折半查找算法实现

❶ 数据结构 顺序查找算法和折半查找算法

解答：
查找key=41的算法：折半查找法 比较次数：3次
查找key=35的算法：顺序查找法 比较次数：6次
顺序查找算法实现代码：
int SequenceSearch(int a[], int n, int key)
{
int i=0,cnt=0;
for (i=0; i<n; i++)
{
cnt++;

if (a[i] == key)
{
printf("\nSequencial Search compare times:%d",cnt);
return key ;
}
}
return -1;
}
l折半查找算法实现代码：
int BinarySearch(int a[], int n, int key)
{
int low=0,high=n-1,mid=0;
int cnt=0;
while (low<=high)
{
cnt++;
mid = (low+high)/2;
printf("\ncompare %d with %d",a[mid],key);
if (a[mid] == key)
{
printf("\nSequencial Search compare times:%d",cnt);
return key;
}
if (a[mid]>key)
{
high=mid-1;
}
else
{
low = mid+1;
}
}
return -1;
}

❷ 数据结构折半查找算法的方法

041424344#include <stdio.h> int Dichotomy(int a[],int _value,int n){ // 二分法(也称折半查找法) int index=0; // 当前数组的首元素下标 int current=n-1; // 数组当前的大小 int k; // 当前数组中间的数的下标 while (index<current) { // 开始二分法查找 k=(index+current)/2; // 除以2代表得到当前数组中间的数的下标 if(a[k]==_value) return k; // 返回要查找的值_value所在的下标 // 否则比较要查找的值_value是在折半后的前半部分还是后半部分 if(a[k]<_value){ // 说明要查找的值在折半后的后半部分 index=k+1; // 令index指向后半部分数组的首元素 } else{ // 说明要查找的值在折半后的前半部分 current=k-1; // 令current等于前半部分数组的长度 } } return -1; // 返回-1代表没有查找到该值(_value)}void main(){ int arr[5]={2,12,45,87,95};// 前提是一组数组必须是有序数对(即按小到大或大到小) if(Dichotomy(arr,87,5)!=-1) printf("87在数组中对应的下标是:%d\n",Dichotomy(arr,87,5)); else printf("没有找到指定的值\n");}// 用一句话概括二分法(折半查找法)的思想就是:在一组有序对数组中反复折半后得到中间数组的下标,然后再进行是否与要查找的值相等,若相等则返回当前要查找的值的下标。 那么，上面的代码的注释与下面一一对应，它在执行的结果会产生两种情况，第一种,不存在。第二种，存在。先来说说第一种情况 不存在： 1.如果给定要查找的值_value大于数组中最大的数,则index不断增大从而促使while循环终止 2.如果给定要查找的值_value小于数组中最小的数,则current不断减少从而促使while循环终止(你自己可以动手在纸上画一个数组,然后思路跟着代码走就会知道或设单步调试亦可) 第二种情况 存在： 1.要查找的数_value正好是在数组中间.那么就执行了一次循环,当然这也是最理想的效果. 否则反复执行2和3:2.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果小于中间的数则说明_value应该在数组中间的前半部分,那么current=k-1(即令current等于前半部分的长度),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止. 3.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果大于中间的数则说明_value应该在数组中间的后半部分,那么index=k+1(即令index指向后半部分的第一个下标),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止.

❸ 二分查找算法实现（图解）与实例

当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法，二分查找又叫折半查找。

它对要查找的序列有两个要求，一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以，本文假设是升序排列的），二是该序列必须是顺序存储的。

如果一个序列是无序的或者是链表，那么该序列就不芹燃滑能进行二分查找。之所以被查找的序列要满足这样的条件，是由二分查找算法的原理决定的。

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

二分查找能应用于任何类型的数据，只要能将这些数据按照某种规则进行排序。然而，正因为它依赖于一个有序的集合，这使得它在处理那些频繁插入和删除操作的数据集时不太高效。这是因为，对于插入和操作来说，为了保证查找过程正常进行，必须保证数据集始终有序。相对于查找来说，维护一个有序数据集的代价更高。此外，元素必须存储在连续的空间中。因此，当待搜索的集合是相对静态的数据集时，此时使用二分查找段棚是最好的选择。

二分查找算法的原理如下：

二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半嫌腊的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。

二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。

此实现过程的实施是通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。

二分查找的时间复杂度取决于查找过程中分区数可能的最大值。对于一个有n个元素的数据集来说，最多可以进行O(㏒₂n)次分区。对于二分查找，这表示最终可能在最坏的情况下执行的检查的次数：例如，在没有找到目标时。所以二分查找的时间复杂度为O(㏒₂n)。

参考：
https://www.html.cn/qa/other/23018.html

https://www.cnblogs.com/idreamo/p/9000762.html