算法之二分查找法

时间:2022-08-30 11:15:16

二分查找法

1.什么是二分查找法

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。(From Baidu Baike)

2.二分查找的算法要求

①.数据必须有序排列;

②数据必须顺序存储。

3.二分查找的时间复杂度

O()=O(logn)

4.二分查找的实现原理

被查找的数据要先按顺序(这里是从小到大)存储在数组a里,并且知道要查找的数据key。

首先我们定义四个变量,分别为left,right,mid,ret。其中left、right和mid作为指向数组下标的变量,ret储存查找的结果(下标)并返回其值。

查找开始,首先让left和right指向数组的两端,并让ret为-1(返回-1表示没有查找到),求出left和right的中间值mid,比较数组a[mid]与被查找元素key的关系。

①若a[mid] = key,则表示找到被查找元素,查找结束;

②若a[mid] > key,则表示key应该比a[mid] 小,所以让right = mid -1,并继续查找;

③若a[mid] < key,则表示key应该比a[mid] 大,所以让left = mid + 1,并继续查找;


算法之二分查找法

由此可见,整个查找的过程一直在继续,直到找到数据或者查找完数据,那么查找完数据的条件是什么呢?这里直接给出答案,有兴趣的读者可以写一段代码调试查看或者在纸上演算一下。

right > ltft

由上述条件可以得知,查找要放在一个循环里,或者用递归实现。下面给出代码。

5.二分查找的代码

/* Title: 二分查找(循环实现) Author:Pengwill Date:2016-08-29 Blog:http://blog.csdn.net/pengwill97 */
#include<stdio.h>
int main()
{
    int a[] ={1,5,6,8,9,10,15,16,17,51,56};//这里首先定义了一个有序的数组,如果无序,先排序
    int left,right,mid,ret,k;
    ret = -1;//初始化,-1表示没有查找到数据
    left = 0;
    right = sizeof(a)/sizeof(a[0]);
    scanf("%d",&k);//输入要查找的数据
    while(right>left){//注意循环的条件
        mid = (right+left)/2;
        if(a[mid]==k){
            ret = mid;
            break;
        }else if(a[mid] > k){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    printf("%d",ret);
    return 0;
}