【数据结构】二分查找

1.概念

二分查找（Binary Search）是一种高效的查找算法，它在一个有序数组中查找特定的元素。二分查找的工作原理是不断将数组分成两半，比较中间元素与目标值，根据比较结果选择左半部分或右半部分继续查找，直到找到目标元素或数组被完全分割。

二分查找的基本步骤如下：

1. 确定数组的中间位置：mid = (low + high) / 2，其中low是查找区间的起始位置，high是查找区间的结束位置。
2. 比较中间位置的元素array[mid]与目标值target：
   • 如果array[mid]等于target，则查找成功，返回中间位置的索引。
   • 如果array[mid]小于target，则目标值位于中间位置的右侧，将low设置为mid + 1，并重复步骤1。
   • 如果array[mid]大于target，则目标值位于中间位置的左侧，将high设置为mid - 1，并重复步骤1。
3. 当low大于high时，说明目标值不在数组中，查找失败，返回一个特殊值（通常是-1）表示未找到。

二分查找的时间复杂度是O(log n)，其中n是数组的长度。这是因为每次查找都会将查找范围减半，所以查找的次数与n的对数成正比。

二分查找的前提是数组必须是有序的。如果数组无序，则需要先对数组进行排序，然后才能应用二分查找。  

2.示例代码

#include <stdio.h>
#include <stdlib.h>
int findByHalf(int* p, int n, int x)
{
    int low = 0;
    int high =n-1;
    int middle;//用来保存中间位置下标
    while(low <= high)//low > high循环结束
    {
        //1.得到中间位置的下标
        middle = (low + high) / 2;
        //2.x与中间位置的元素做比较,判断在middle位置的左边还是右边,来缩小范围
        if(x == p[middle])
            return middle; //找到了
        else if(x > p[middle])//说明在右侧,需要移动low
            low = middle + 1;
        else //x < p[middle] //说明在左侧,需要移动high
            high = middle - 1;
    }
    //上面的循环结束后,如果都没有执行return middle,说明没有找到
    return -1;
}
int main(int argc, const char *argv[])
{
    int a[8] = {11,22,33,40,55,60,70,89};
    int num;
    scanf("%d",&num);
    int ret = findByHalf(a, 8, num);
    if(ret == -1)
    {    
        printf("没有找到!!\n");
    }
    else
    {
        printf("%d的下标是%d\n",a[ret],ret);
    }
    return 0;
}

结语

以上就是二分查找的使用方法，本次代码分享到此结束，后续还会分享数据结构有关知识。

最后的最后，还请大家点点赞，点点关注，谢谢大家！