博客

什么是二分查找？

首先，二分查找也叫折半查找，它是对于一组有序（升序或降序）数列来说的，我们举例子说明这个思想。

例如：猜数字游戏

随机给出1-100内的一个数字，请猜出这个数字

那我们不能随机没有规律的去猜，这时考虑二分查找的思想

例如38

第一次猜50，告诉你猜大了，那么此时就在1-50内折半

第二次猜25，告诉你猜小了，那么此时就在26-49内折半…以此类推

这就是二分查找的思想。

那么我们如何用c语言来编写实现它呢？

给出一个升序数组arr[10]={0,1,2,3,4,5,6,7,8,9}，要求用二分查找的方法找出4。

那么第一次我们折半找到5，5>4

然后进行第二次折半找到2，2<4

进行第三次折半找到3，3<4

最后一次我们就找到了目标数字4

接下来我们用两种方式实现：

1、（此代码存在安全问题并可以优化）

#include<stdio.h>
int binary_search(int arr[], int num, int sz)//二分查找函数
{
    int mid = 0;//折半后数字的下标
    int left = 0;//左下标
    int right = sz - 1;//右下标
    while (left <= right)//判断当左下标小于右下标条件满足
    {
        mid = (left + right)/2;//找出折半后数字下标(尽量不要用此方法)
        if (num <arr[mid])
            right = mid;
        else if (num > arr[mid])
            left = mid;
        else
            return mid;//找到目标数字并返回数组下标
    }
    return -1;//左下标大于右下标没找到
}
int main()
{
    int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int num = 3;
    int sz = sizeof(arr) / sizeof(arr[0]);//求这个数组的大小
    int tmp = binary_search(arr,num,sz);
    if (tmp != -1)
        printf("exist the number is:%d", tmp);
    else
        printf("no exist!");
    return 0;
}

2、这个代码更具体是代码一的优化 给出左右下标在这个范围内查找

#include<stdio.h>
int binary_search(int arr[], int left, int right, int  num)//二分查找函数 给出做右下标在此范围内找
{
    int mid = 0;
    while (left <= right)
    {
        mid = left + ((right - left) >> 1);//这样求中间的数的下标等安全>>为右移符号，右移1等于除以2
        if (num <arr[mid])
            right = mid;
        else if (num > arr[mid])
            left = mid;
        else
            return mid;
    }
    return -1;
}

int main()
{
    int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int num = 3;
    int tmp = binary_search(arr, 0, 6, num);
    if (tmp!=-1)
        printf("exist the number is:%d", tmp);
    else
        printf("no exist!");
    return 0;
}