前言

  小张是一名大三的大学生，最近面试了腾讯、字节跳动等公司，面试结果不佳。发现自己的数据结构和算法知识还不够扎实吧，还需要认真的复习一遍。因此在这里记录一下自己的学习过程。算是自己的学习笔记吧，也希望这些文字能够给读者们一些帮助吧。

正文

什么是二分查找？

  二分查找是用于有序数组的查找算法，时间复杂度为log(N)

  二分查找其实源于我们小时候玩的“猜数字”的游戏。例如，小明同学在心里想一个范围在1～1000之间的整数，小美同学说出自己猜的数字后，小明同学会告诉小美是大了，小了还是正好猜中了。小明每一次的提示，其实就是把数字的范围给缩小了。二分查找的道理也是相同的，它充分利用了数组有序的性质，每一次查找都将数字范围缩小了一半。这比从1～1000按顺序去猜数字效率高很多。

二分查找的代码实现

public static int binarySearch(int[] nums, int target) {
        if(nums == null || nums.length == 0)
            return -1;
        int low = 0;
        int high = nums.length;
        while(low < high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] > target)
                high = mid;
            else
                low = mid + 1;
        }
        return low;
    }

下界:0 上界:nums.length，它表示的查找范围为[0,nums.length) 左开右闭，因此当low == high时查找就结束了,[low,high)中就不再包含任何数字了。

举个例子来说：

二分查找Found.png

二分查找NotFound.png

可见
1.当找到target时，二分查找能够返回target的索引。
2.当找不到target时，二分查找返回这样一个索引值，当把target值插入到数组中的该索引值的位置时，保持该数组仍然有序。

二分查找基础版本的反思

  二分查找的基础版本没有问题，可是当我们查找的target在数组中有多个时，二分查找会返回什么数值呢？是第一个，还是中间的，还是最后一个？仔细思考以后可以得出都不是。那么我们如何写出稳定的算法来找到第一个target和最后一个target呢？

找到第一个target的二分搜索

public int binarySearch_bottom(int[] nums, int target) {
        if(nums == null || nums.length == 0)
            return -1;
        int low = 0;
        int high = nums.length;
        int mid = 0;
        while(low < high){
            mid = (low + high) / 2;
            if(target <= nums[mid])
                high = mid;
            else
                low = mid + 1;
        }
        return low;
    }

1.当nums[mid] == target时：答案可能是mid或者在mid的左边，因此high = mid
2.当nums[mid] > target时：答案可能在mid的左边，因此high = mid
3.当nums[mid] < target时：答案只可能在mid的右边，因此low = mid + 1
因此将这些条件合并起来，就得到了上述的代码。

返回值的分析：
1.当找到target时，二分查找能够返回最左边的target的索引。
2.当找不到target时，二分查找返回这样一个索引值，当把target值插入到数组中的该索引值的位置时，保持该数组仍然有序。

同理我们可以得到找到最后一个target的二分搜索

public static int binarySearch_upper(int[] nums, int target) {
        if(nums == null || nums.length == 0)
            return -1;
        int low = 0;
        int high = nums.length;
        int mid = 0;
        while(low < high){
            mid = (low + high) / 2;
            if(target >= nums[mid])
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }

和上一个算法的原理是一样的，但是求target上界的算法要特别注意一下它的返回值。

返回值的分析：
1.当找到target时，二分查找能够返回最右边的target的索引加上一。
2.当找不到target时，二分查找返回这样一个索引值，当把target值插入到数组中的该索引值的位置时，保持该数组仍然有序。

小结

今天的学习就到这里啦，第一次写简书，如果对你的学习有帮助的话，可以支持一下我呀。