算法学习—二分查找

1、二分查找的概念

当我们碰到需要获取数列中的元素或者利用数列中的元素时，最快想到的方法就是通过顺序查找，一个一个找下去，这种查找方式基本上市从头开始到末尾，将所有的元素都找一遍，直到找到了想要的元素。
这种方法因为是需要查找所有的元素，所以当元素数量太多的时候，就会出现超时的情况出现，效率十分低下，所以一般实际的情况下我们不是用顺序查找。
取而代之的，是二分查找。二分查找顾名思义，就是将一个数列分成两个部分，分别查找元素。虽然说该种方法比较高效，但是这种方法是建立在数列有序的基础上的，所以对于一些不能排序的数列，可能不适用二分查找；除此之外，二分查找的结果只能是一个，不能是多个。

2、基本思想

二分查找的基本思想是：我们首先定义两个首尾元素，一般一开始默认是在数列的第一位以及最后一位。然后我们找到两个首尾元素的中间点元素 mid ，将该元素与我们作为比较的元素相对比，然后决定我们下一步所取的数列的区间范围。而在所取范围之外的另一半的元素我们自然就不用再查找了，效率就大大地提高了。

3、解题步骤

1.将数列排序
2.通过首尾节点确定中间点元素 mid
3.将mid与比较的元素相对比，判断下一次所取的区间
4.最后只剩下一个结果时，结束

4、二分查找的模板

4.1、第一类：数据无重复查找数据

所要查找的数据如下所示：

位置：0 1 2 3 4 5 6 7 8 9
数据：1 2 3 4 5 6 7 8 9 10

代码：

public int binarySearch(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left < right) {
        int middle = left + (right - left) / 2;
        if (numbers[middle] == target) {
            return middle;
        }else if (numbers[middle] > target) {
            right = middle - 1;
        }else {
            left = middle + 1;
        }
    }
    return -1;
}

4.2、第二类：数据有重复查找小于该数的最后一个数字的位置

位置：0 1 2 3 4 5 6 7 8 9
数据：1 1 2 2 3 3 3 3 4 4

在本类型中，我们查找小于3的最后一个数据的位置。

代码：

public int binarySearch(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left < right) {
        int middle = left + (right - left + 1) / 2;
        if (numbers[middle] == target) {
            right = middle - 1;
        }else if (numbers[middle] > target) {
            right = middle - 1;
        }else {
            left = middle;
        }
    }
    return left;
}

4.3、第三类：数据有重复查找该数字第一次出现的位置

位置：0 1 2 3 4 5 6 7 8 9
数据：1 1 2 2 3 3 3 3 4 4

在本类中，我们查找数字3第一次出现的位置。

public int binarySearch(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left < right) {
        int middle = left + (right - left) / 2;
        if (numbers[middle] == target) {
            right = middle;
        }else if (numbers[middle] > target) {
            right = middle;
        }else {
            left = middle + 1;
        }
    }
    return left;
}

4.4、第四类：数据有重复查找该数字最后一次出现的位置

位置：0 1 2 3 4 5 6 7 8 9
数据：1 1 2 2 3 3 3 3 4 4

在本类中，我们查找数字3最后一次出现的位置。

public int binarySearch(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left < right) {
        int middle = left + (right - left + 1) / 2;
        if (numbers[middle] == target) {
            left = middle;
        }else if (numbers[middle] > target) {
            right = middle - 1;
        }else {
            left = middle;
        }
    }
    return left;
}

4.5、第五类：数据有重复查找第一个大于该数的数字的位置

位置：0 1 2 3 4 5 6 7 8 9
数据：1 1 2 2 3 3 3 3 4 4

在本类中，我们查找第一个大于数字3的数字的位置。

public int binarySearch(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left < right) {
        int middle = left + (right - left ) / 2;
        if (numbers[middle] == target) {
            left = middle + 1;
        }else if (numbers[middle] > target) {
            right = middle;
        }else {
            left = middle + 1;
        }
    }
    return left;
}

5、实际例子

5.1、搜索插入位置

leetcode-35

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

示例1：

1 2	输入: nums = [1,3,5,6], target = 5 输出: 2

示例2：

1 2	输入: nums = [1,3,5,6], target = 2 输出: 1

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

解题思路：

该题目的意思是在数列中找到一个目标值，并返回其索引，所以该题符合类型一的情况。
我们假设该位置为 pos ，所以有成立的条件为：
$$
nums[pos−1]<target≤nums[pos]
$$
其中 nums 代表排序数组。由于如果存在这个目标值，我们返回的索引也是 pos，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于 target 的下标」。

完整代码：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left=0,right=nums.length;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>=target){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
}

5.2、x 的平方根

leetcode-69

给你一个非负整数 x ，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例1：

1 2	输入：x = 4 输出：2

示例2：

1
2
3

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

1	0 <= x <= 231 - 1

解题思路：
由于 x 平方根的整数部分 ans 是满足k的平方小于等于x的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。

二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 xx 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 ans 后，也就不需要再去尝试 ans+1 了。

完整代码：

class Solution {
    public int mySqrt(int x) {
        int left=0;
        int right=x;
        int num=-1;
        while (left<=right){
            int mid=(left+right)/2;
            if ((long)mid*mid<=x){
                num=mid;
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return num;
    }
}