C语言—二分查找(折半查找)

写在前面

实现二分查找的条件1、要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列。通俗来说所查找的数列或内容逻辑上必须有序。2、查找的数量是一个而不是多个

基本思路:1、定义一维数组a储存有序数据left、right分别为第一个(左)和最后一个数组元素的下标。数组取值对应的是下标数组的第一个下标是从0开始那么右下标为元素个数-1。

2、循环入口判断left是否大于right。由于left一直在增加而right一直在减少直到最终查找出元素若left <=right且未查找出指定元素时循环继续进行。如果大于则退出循环。

3、若目标值key大于a[mid]说明key比a[mid]左边的值都要大下一次循环舍去左边的值left=mid+1;同理如果key小于a[mid]说明key小于a[mid]右边的所有值统统舍去right=mid-1。直到key=a[mid]或者left>right循环结束。

示例设某数组里面的元素个数为{123456789}所查找的数为7。

第一次查找 mid=left+right/2 mid==下标为4对应元素5 小于我们查找的数那么把中间下标加一之后赋值给left==下标为4+1右下标不变。此时没查找的元素为5 6 7 8 9

第二次查找 mid=left+right/2 mid==下标为7对应元素8 大于我们查找的数那么把中间下标减一之后赋值给right==下标为7-1那么此时查找的范围为 下标为5 6的数

第三次查找 mid=left+right/2 mid==下标为5 小于我们查找的数那么把中间下标加一之后赋值给left==下标为5+1

第四次查找 mid=left+right/2 mid==下标为6对应元素7

代码

#include<stdio.h>
void binarysearch(int *a,int sum,int n)
{
    int left=0,mid=0,count=0;
    int right=sum-1;
    int key=n; // 对最小数组下标最大下标目标值中间值以及计数器的声明
    while(left<=right){
        count++;
        mid=(left+right)/2;
        if(key>a[mid])
            left=mid+1;  //
        else if(key<a[mid])
            right=mid-1;
        else if(key==a[mid]){
            printf("Success!\nAfter %d tries\na[%d]=%d",count,mid,key); 
            return ;
        }
    }
    printf("No found");
}
int main(void)
{
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    printf("请输入你想要查找的数字\n");
    int n;
    scanf("%d",&n);
    binarysearch(a,10,n);
} 

注意

1)计算 mid 时 ,最好不使用 (left + right )/ 2,建议使用mid = left + (right - left) / 2否则有可能会导致溢出

2while (left < = right) { } 注意括号内为 left <= right ,而不是 left < right 如果我们设置条件为 left < right 则当我们执行到最后一步时则我们的 left 和 right 重叠时则会跳出循环返回 -1区间内不存在该元素但 left 和 right 此时指向的可能就是目标元素

3left = mid + 1,right = mid - 1 而不是 left = mid 和 right = mid。否则可能会进入死循环。