二分查找逻辑

二分查找

二分查找是我们经常使用的一种算法，他的逻辑是

在升序或者降序且无重复元素的数组中，比较目标值和数组中间值的方法，每次缩小一半的搜索范围，相比遍历可以加快计算的速度

查找逻辑

假设：目标值为下标为4的数值，给定一个大小为10的数组，我们给定他的下界left=0，上界right=numsLen-1，中间下标mid=（left+right）/2

判断目标值target是否等于num[mid]；

• 如果相等则返回mid

如果不相等则判断target与num[mid]的大小关系；

• target>num[mid]；则说明目标值在后半部分，因为mid与目标值不相等，那么left就变成mid+1；
• target<num[mid]；则说明目标值在前半部分，因为mid与目标值不相等，那么right就变成mid-1；

每次缩小范围后都需要继续执行上述步骤，我们可以使用一个while循环，当left<right的时候循环，直到找到目标值对应的下标，返回下标；或者没有目标值对应的下标，返回-1；

题目练习

我们找到一个题目来练习一下

题目描述

牛客网的题目链接： 二分查找-I_牛客题霸_牛客网 (nowcoder.com)

代码示例

根据二分查找的逻辑，我们可以写下代码：

int search(int* nums, int numsLen, int target ) {
    if(nums==NULL){
        return -1;
    }
    int left=0;
    int right=numsLen-1;
    int mid=(left+right)/2;
    while (left<=right) {
        if (nums[mid]>target) {
            right=mid-1;
        }
        else if (nums[mid]<target) {
            left=mid+1;
        }
        else
        return mid;
        mid=(left+right)/2;
    }
    return -1;
}

总结

二分查找是我们必须掌握的一种算法，继续加油吧！

多多重复，百炼成钢！

小杜陪各位一起成长！