基础二分查找

先上代码

//查找value对应下标，找不到返回-1
int binarySearch(int arr[], int length, int value) {
    int middle, low, high;
    low = 0;
    high = length - 1;

    while(low <= high) {
        middle = low + ((high - low) >> 1);
        if (arr[middle] == value)
        {
            return middle;
        } else if(arr[middle] > value) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }

    return -1;
}

时间复杂度: log(n)
二分查找只能作用在有序数组中

核心思想

取出数组最中间的数，与要查找的值做比较，会有如下3种情况。

1. 中间数等于查找数 直接返回下标
2. 中间数大于查找数，说明要查找的数只可能出现在中间数的左边。
3. 中间数小于查找树，说明要查找的数只可能出现在中间数的右边。
   有了上面三种情况，我们就可以不断缩小查找范围。
   直至找到查找数，或者取得查找数不存在数组中。

一步一步实现二分查找

定义中间数下标，起始下标。

int binarySearch(int arr[], int length, int value)  {
    //中间 开始 结束
    int middle, low, high;
    low = 0;
    high = length - 1;
}

终止条件

int binarySearch(int arr[], int length, int value)  {
    //中间 开始 结束
    int middle, low, high;
    low = 0;
    high = length - 1;
    //low 如果大于 high 说明查找数不存在数组中
    while(low <= high) {

    }

    return -1;
}

计算中间数下标,判断中间数的大小

int binarySearch(int arr[], int length, int value)  {
    //中间 开始 结束
    int middle, low, high;
    low = 0;
    high = length - 1;
    //low 如果大于 high 说明查找数不存在数组中
    while(low <= high) {
        //中间数的下标
        middle = low + ((high - low) >> 1);
        //判断中间数与查找数的关系
        if(arr[middle] == value) {
            //相等就直接返回下标
            return middle;
        } else if (arr[middle] > value) {
            //大于就说明查找数可能出现在中间数左边，减小high
            high = middle - 1;
        } else {
            //小于就说明查找数可能出现在中间数右边，加大low
            low = middle + 1;
        }
    }

    return -1;
}

二分查找代码到这就完成了是不是很简单，但是一定要注意细节啊

都看到这了，点个赞再走啊~