折半查找法

先看看这个，下面有例子折半查找：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法要求算法复杂度下面提供一段二分查找实现的伪代码:BinarySearch(max,min,des)mid-<(max+min)/2while(min<=max)mid=(min+max)/2if mid=des thenreturn midelseif mid >des thenmax=mid-1elsemin=mid+1return max折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。

它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。

如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。

如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

二分查找法一般都存在一个临界值的BUG，即查找不到最后一个或第一个值。

可以在比较到最后两个数时，再次判断到底是哪个值和查找的值相等。

C语言代码int BinSearch(SeqList * R，int n , KeyType K ){ //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1int low=0，high=n-1，mid；//置当前查找区间上、下界的初值if(R[low].key==K){return low ;}if(R[high].key==k)return high;while(low<=high){ //当前查找区间R[low..high]非空mid=low+((high-low)/2)；//使用(low + high) / 2 会有整数溢出的问题（问题会出现在当low + high的结果大于表达式结果类型所能表示的最大值时，这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)不存在这个问题if(R[mid].key==K){return mid；//查找成功返回}if(R[mid].key>K)high=mid-1; //继续在R[low..mid-1]中查找elselow=mid+1；//继续在R[mid+1..high]中查找}if(low>high)return -1；//当low>high时表示查找区间为空，查找失败} //BinSeareh折半查找程序举例程序要求：1.在main函数中定义一个20个元素的int数组，完成初始化和显示操作。

折半查找法c语言折半查找法，又称二分查找法，是一种在有序数据集（顺序表/列表、数组等）中，快速查找指定值的高效算法。

折半查找法的思想是基于二分法思想，用“分而治之”的思想来快速查找指定值。

折半查找法是一种最常用的查找方法，它也被称为是一种“有序”查找，因为要查找的数据必须是已经排好序的。

实际上，折半查找法的实现只要将有序的数据列折半，一次比较即可将待查找的值与被折半的数据列比较，这样查找的过程会比较快捷。

下面就来介绍折半查找法的具体实现方式：折半查找法假设要查找的数据是一个有序数列，在这里以升序数列为例：（1）先定义一个指向待查找序列低位的索引，称之为low；（2）定义另一个指向待查找序列高位的索引，称之为high；（3）首先用low与high计算中位索引 mid，将这个中位索引处的值与要查找的数据进行比较，如果相等，则搜索成功；（4）如果不等，则根据要查找的数据与中位索引处的值的比较结果，将待查找的序列分为两部分，下次查找只要在其中一部分序列中继续进行折半查找即可。

有了上面的思路，我们就可以用c语言来实现折半查找法了。

代码如下：#include<stdio.h>int binary_search(int arr[], int n, int key){int low, mid, high;low = 0;high = n-1;while(low <= high){mid = (low + high) / 2;if(arr[mid] == key)return mid;else if(arr[mid] > key)high = mid - 1;elselow = mid + 1;}return -1;}int main(){int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int res = binary_search(arr, 10, 7);printf(res = %d res);return 0;}以上就是一个最基本的折半查找法的实现，通过定义一个low、high和mid三个索引，在计算中位索引mid时，low和high 分别指向有序数列的低位和高位，根据判断条件，如果要查找的值等于中位索引处的数据，则查找成功，否则就用待查找的数据与中位索引处的数据进行比较，来确定下一次查找的范围。

二分查找是在我们整个数据结构当中一个比较重要的算法，它的思想在我们的实际开发过程当中应用得非常广泛。

在实际应用中，有些数据序列是已经经过排序的，或者可以将数据进行排序，排序后的数据我们可以通过某种高效的查找方式来进行查找，今天要讲的就是折半查找法(二分查找)，它的时间复杂度为O(logn)，将以下几个方面进行概述了解二分查找的原理与思想分析二分查找的时间复杂度掌握二分查找的实现方法了解二分查找的使用条件和场景1 二分查找的原理与思想在上一个章节当中，我们学习了各种各样的排序的算法，接下来我们就讲解一下针对有序集合的查找的算法—二分查找（Binary Search、折半查找）算法，二分查找呢，是一种非常容易懂的查找算法，它的思想在我们的生活中随处可见，比如说：同学聚会的时候喜欢玩一个游戏——猜数字游戏，比如在1-100以内的数字，让别人来猜从，猜的过程当中会被提示是猜大了还是猜小了，直到猜中为止。

这个过程其实就是二分查找的思想的体现，这是个生活中的例子，在我们现实开发过程当中也有很多应用到二分查找思想的场景。

比如说仙现在有10个订单，它的金额分别是6、12 、15、19、24、26、29、35、46、67 请从中找出订单金额为15的订单，利用二分查找的思想，那我们每一次都会与中间的数据进行比较来缩小我们查找的范围，下面这幅图代表了查找的过程，其中low，high代表了待查找的区间的下标范围，mid表示待查找区间中间元素的下标（如果范围区间是偶数个导致中间的数有两个就选择较小的那个）第一次二分查找第二次二分查找第三次二分查找通过这个查找过程我们可以对二分查找的思想做一个汇总：二分查找针对的是一个有序的数据集合，查找思想有点类似于分治思想。

每次都通过跟区间的中间元素对比，将待查找的区间范围缩小为原来的一半，直到找到要查找的元素，或者区间被缩小为0。

一：查找的数据有序二：每次查找，数据的范围都在缩小，直到找到或找不到为止。

折半查找的判定树的构造方法折半查找，也被称为二分查找，是一种在有序数组中查找特定元素的算法。

构造折半查找的判定树可以帮助理解算法的执行过程。

下面是关于构造折半查找判定树的50条方法，并且会对每一条进行详细描述。

1. 在有序数组中选择中间元素作为根节点。

构造方法详解：我们在有序数组中选择中间元素作为根节点。

这个中间元素是数组中间位置的值。

这一步是构造判定树的第一步，因为它将分割数组成左右两个子数组。

2. 在根节点的左侧选择一个中间元素作为左子树的根节点。

构造方法详解：在根节点的左侧选择一个中间元素，作为左子树的根节点。

这个中间元素是根节点左侧子数组的中间位置的值。

这一步扩展了判定树，使得左侧的子数组也可以进行折半查找。

3. 在根节点的右侧选择一个中间元素作为右子树的根节点。

构造方法详解：同样地，在根节点的右侧选择一个中间元素，作为右子树的根节点。

这个中间元素是根节点右侧子数组的中间位置的值。

这一步扩展了判定树，使得右侧的子数组也可以进行折半查找。

4. 重复以上过程，依次构造左右子树。

构造方法详解：依次对左右子树进行重复的选择中间元素作为子树的根节点的过程。

这样不断地构造子树，直到数组中的每个元素都被考虑到。

5. 当子数组中只剩下一个元素时，将其作为叶子节点添加到判定树中。

构造方法详解：当子数组中只剩下一个元素时，将其作为叶子节点添加到判定树中。

这表示整个有序数组的判定树构造完成。

因为此时的子数组不再能够被分割，所以将其作为叶子节点。

6. 对每个子数组的根节点和叶子节点进行连接，构成完整的判定树结构。

构造方法详解：对每个子数组的根节点和叶子节点进行连接，构成完整的判定树结构。

这意味着将每个子数组的根节点和叶子节点沿着判定树的路径连接起来，形成一棵完整的树结构。

7. 确定根节点、左右子树的取值范围，并进行标记。

构造方法详解：对于每个节点，包括根节点和叶子节点，需要确定其对应的子数组的取值范围，并进行标记。

c语言折半查找法代码折半查找法，也称二分查找法，是一种高效的查找算法。

它的基本思想是将有序数组分成两部分，通过比较中间元素和目标元素的大小关系，来确定目标元素在哪一部分中，然后再在该部分中继续进行查找，直到找到目标元素或者确定目标元素不存在为止。

下面是C语言实现折半查找法的代码：```#include <stdio.h>int binarySearch(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};int n = sizeof(arr) / sizeof(arr[0]);int target = 7;int index = binarySearch(arr, 0, n - 1, target);if (index == -1) {printf("目标元素不存在\n");} else {printf("目标元素在数组中的下标为：%d\n", index);}return 0;}```在上面的代码中，binarySearch函数接收四个参数：数组arr、左边界left、右边界right和目标元素target。

它通过while循环不断缩小查找范围，直到找到目标元素或者确定目标元素不存在为止。

其中，mid表示当前查找范围的中间位置，通过比较arr[mid]和target的大小关系来确定目标元素在哪一部分中。

具有12个关键字的有序表,折半查找的平均查
找长度
折半查找是一种在有序序列中查找某个给定值的方法，它是一种加速搜索的算法，并且有着高效、可靠的特点，在每次搜索次数减半的情况下，无论序列的长度多大，其查找代价是固定的，能大大减少存储器和 CPU 占用，节省时间和空间。

折半查找时，先取出中间位置记录，将查找值和中间位置记录进行比较，子表长度缩小，重复上述查找操作，直到找到等于查找值的记录，或子表不存在为止。

如果有12个关键字的有序表，用折半查找方法来查找，那么平均查找长度(ASL)是[log2(n)]+1=4。

从0开始计数，折半查找找到元素最多需要3步：第一步，查找中间位置的元素；第二步，比较查找元素与中间位置的元素的大小，如果查找元素小于中间位
置的元素，就在中间位置的左半边的子序列中继续查找；如果查找元素大于中间位置的元素，就在中间位置的右半边的子序列中继续查找；第三步，不断进行折半查找，直到找到查找元素，或者查找范围为空，则查找失败，结束。

总的来说，折半查找是一种非常有效的搜索算法
它可以在有序表中大大加快搜索速度，在12个关键字有序表中，折半查找的平均查找长度是4，在节省时间和空间的同时，能够很好地用于搜索、匹配等需要的操作中。

二分法的算法描述
二分法算法描述
二分法是一种常用的算法，也称为折半查找法。

它的基本思想是将一个有序的数组分成两个部分，然后判断目标值在哪个部分，再在该部分中继续进行查找，直到找到目标值或者确定目标值不存在为止。

二分法的算法描述如下：
1. 首先，确定数组的左右边界，即左边界为0，右边界为数组长度减1。

2. 然后，计算出数组的中间位置，即中间位置为左右边界之和除以2。

3. 接着，判断目标值与中间位置的值的大小关系，如果目标值小于中间位置的值，则在左半部分继续查找，否则在右半部分继续查找。

4. 如果目标值等于中间位置的值，则直接返回中间位置。

5. 如果左右边界相遇，但是目标值仍未找到，则说明目标值不存在，返回-1。

6. 如果目标值在左半部分，则将右边界设为中间位置减1，继续执行步骤2。

7. 如果目标值在右半部分，则将左边界设为中间位置加1，继续执行步骤2。

二分法的时间复杂度为O(log n)，比线性查找的时间复杂度O(n)要快得多。

因此，在需要查找有序数组中的元素时，二分法是一种非常高效的算法。

二分法的应用场景很多，例如在搜索引擎中，可以使用二分法来查找关键词在文档中的位置；在游戏中，可以使用二分法来查找玩家的位置等等。

二分法是一种非常实用的算法，可以大大提高查找效率，值得我们在编程中多加应用。

二分查找算法（折半查找算法）
二分查找算法也称折半查找算法，是在有序数组中查询其中一特定元
素的算法。

它的基本思想是：将数组中间位置的元素与要查找的元素比较，如果两者相等，则查找成功；如果要查找的元素小于中间位置元素，则在
数组的前半部分查找；如果要查找的元素大于中间位置元素，则在数组的
后半部分查找。

它采用分而治之的思想，基于这个思想，将一个庞大的问题划分成规
模较小的子问题分别解决，然后将子问题的解组合起来构成原问题的解。

具体而言，就是将要查找的元素(也就是目标值)与数组的元素对比，每次
都只比较一部分，直到确定位置，也就是找到目标值，此时查询结束。

实现二分查找算法的基本步骤如下：
（1）首先，从有序数组的中间元素开始，将中间元素与要查找的元
素进行比较；
（2）如果查找的元素正好是中间元素，则查找成功；
（3）如果查找的元素小于中间元素，则在数组的前半部分查找；
（4）如果查找的元素大于中间元素，则在数组的后半部分查找；
（5）重复上面的步骤，直到查找到指定的元素或者查找范围为空为止。

二分查找法，也称为折半查找法，是一种在有序数组中查找特定元素的算法。

它的要求如下：
1. 数组必须是有序的：二分查找法只能在有序数组中进行查找，如果数组无序，需要先进行排序。

2. 数组必须是静态的：二分查找法适用于静态数组，即不会频繁插入或删除元素的数组。

如果数组需要频繁修改，建议使用其他数据结构。

3. 数组元素必须可比较：二分查找法依赖于元素之间的比较操作，因此数组元素必须支持比较操作。

对于自定义类型的元素，需要实现比较操作符。

4. 查找范围必须确定：二分查找法需要明确查找范围的起始和结束位置，通常使用两个指针来表示。

5. 查找范围必须缩小：二分查找法通过不断缩小查找范围来逼近目标元素，直到找到目标元素或确定目标元素不存在。

总结起来，二分查找法的要求是有序数组、静态数组、可比较元素、确定查找范围和缩小查找范围。

折半查找算法思想：将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。

通过一次比较，将查找区间缩小一半。

折半查找是一种高效的查找方法。

它可以明显减少比较次数，提高查找效率。

但是，折半查找的先决条件是查找表中的数据元素必须有序。

算法步骤描述：step1 首先确定整个查找区间的中间位置mid = （left + right ）/ 2step2 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功若大于，则在后（右）半个区域继续进行折半查找若小于，则在前（左）半个区域继续进行折半查找Step3 对确定的缩小区域再按折半公式，重复上述步骤。

最后，得到结果：要么查找成功，要么查找失败。

折半查找的存储结构采用一维数组存放。

折半查找算法举例对给定数列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。

折半查找的算法讨论：优点: ASL≤log2n，即每经过一次比较,查找范围就缩小一半。

经log2n 次计较就可以完成查找过程。

缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。

另外，顺序存储结构的插入、删除操作不便利。

#include <iostream>using namespace std;int Find_Half_Line(int low,int high,int Find_Name,int a[])...{while(low <= high)...{int mid = (low + high)/2;if(a[mid] == Find_Name) //如果相等则返回return mid;elseif(Find_Name > a[mid]) //大于查找值最低的值变为折半中间的值low =mid+1;else high=mid-1; //小于最大值变为中间值}return -1;}int main()...{int Find_Name;int low=0,high=9;int a[10]=...{2,3,5,8,10,12,15,17,19,20};cin >> Find_Name;cout <<Find_Half_Line(low,high,Find_Name,a);return 0;}插入排序插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。