[算法] 优选算法(五):二分查找(上)_算法

1. 二分查找(难度:🟢1度)

题目描述

算法原理
a. 定义left ,right 指针，分别指向数组的左右区间。
b. 找到待查找区间的中间点mid,找到之后分三种情况讨论：
i. arr[mid] == target 说明正好找到，返回mid 的值；
ii. arr[mid] > target 说明[mid, right] 这段区间都是大于target 的，因此舍去右边区间，在左边[left, mid -1] 的区间继续查找，即让right = mid - 1 ，然后重复2 过程；
iii. arr[mid] < target 说明[left, mid] 这段区间的值都是小于target 的，因此舍去左边区间，在右边[mid + 1, right] 区间继续查找，即让left = mid + 1，然后重复2 过程；
c. 当left 与right 错开时，说明整个区间都没有这个数，返回-1
代码实现

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

[注意事项]

计算mid的时候,没有使用(left+right)/2,而是使用left+(right-left)/2的形式.
二分法一般采用最中间的点作为划分点,其他的等分点也可以作为划分点,但是查找效率没有中间作为划分点高.

朴素二分模版总结

//首先定义left和right指针
while (left <= right){
	int mid = left+(right-left)/2;
	if(...) left = mid+1;
	else if(...) right = mid-1;
	else return ...;
}

2. 在排序数组中查找元素的第一个和最后一个位置(难度:🟡3度)

oj链接

题目描述

算法原理
方便叙述，用x 表示该元素，resleft 表示左边界，resright 表示右边界
- 寻找左边界
  我们注意到以左边界划分的两个区间的特点：
  ▪ 左边区间[left, resleft - 1] 都是小于x 的；
  ▪ 右边区间（包括左边界） [resleft, right] 都是大于等于x 的；
  • 因此，关于mid 的落点，我们可以分为下面两种情况：
  ◦ 当我们的mid 落在[left, resleft - 1] 区间的时候，也就是arr[mid] < target 。说明[left, mid] 都是可以舍去的，此时更新left 到mid + 1 的位置，这里需要注意在left上+1,因为mid左边的元素都已经小于目标值了,都可以舍去.继续在[mid + 1, right] 上寻找左边界；
  ◦ 当mid 落在[resleft， right] 的区间的时候，也就是arr[mid] >= target 。说明[mid + 1, right] （因为mid 可能是最终结果，不能舍去）是可以舍去的，此时更新right 到mid 的位置，由于mid的位置可能是最终的值,所以mid位置不可以舍去,不需要-1继续在[left, mid] 上寻找左边界；
  • 由此，就可以通过⼆分，来快速寻找左边界；
  [注意] 循环条件判断必须是left < right,如果加上等号,当找到目标值的时候.left和right重合,第一重合就证明已经找到了目标值,就没有必要再执行操作了,第二,如果找到了目标值,left和right依然会满足条件,会进入循环,会让程序陷入死循环.求中点的时候,必须采用向下取整的方式,如果采用向上取整,如果找到了目标值,right=mid的时候,right没有移动,就会陷入死循环.
- 寻找右边界
  与寻找左边界同理
  ◦ 用resright 表示右边界；
  ◦ 我们注意到右边界的特点：
  ▪ 左边区间（包括右边界） [left, resright] 都是小于等于x 的；
  ▪ 右边区间[resright+ 1, right] 都是大于x 的；
  • 因此，关于mid 的落点，我们可以分为下面两种情况：
  ◦ 当我们的mid 落在[left, resright] 区间的时候，说明[left, mid - 1]（ mid 不可以舍去，因为有可能是最终结果）都是可以舍去的，此时更新left 到mid 的位置；
  ◦ 当mid 落在[resright+ 1, right] 的区间的时候，说明[mid, right] 内的元素是可以舍去的，此时更新right 到mid - 1 的位置；
  • 由此，就可以通过⼆分，来快速寻找右边界；
代码实现

class solution {
    public int[] searchrange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] array = new int[2];
        array[0] = -1;
        array[1] = -1;
        if (nums.length == 0){//注意处理特殊情况
            return array;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;//left下标不可能是t的值
            } else {
                right = mid;//right下标有可能是t的值
            }
        }
        if (nums[left] == target){
            array[0] = left;
        }else{
            return array;
        }
        left = 0;
        right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                right = mid - 1; //right下标不可能是t的值
            } else {
                left = mid;//left下标可能是t的值
            }
        }
        array[1] = right;
        return array;
    }
}

查找边界二分算法模版

左边界

while(left < right){
	int mid = left+(right-left)/2;
	if(...) left = mid+1;
	else right = mid;
}

右边界

while(left < right){
int mid = left+(right-left+1)/2;
if(...) left = mid;
else right = mid-1;
}

3. 搜索插入位置(难度:🔵2度)

oj链接

题目解析

算法原理
a. 分析插⼊位置左右两侧区间上元素的特点：
设插⼊位置的坐标为 index ，根据插⼊位置的特点可以知道：
• [left, index - 1] 内的所有元素均是小于 target 的；
• [index, right] 内的所有元素均是大于等于 target 的。
b. 设 left 为本轮查询的左边界， right 为本轮查询的右边界。根据 mid 位置元素的信息，分析下⼀轮查询的区间：
▪ 当 nums[mid] >= target 时，说明 mid 落在了 [index, right] 区间上，mid 左边包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [left,mid] 上。因此，更新 right 到 mid 位置，继续查找。
▪ 当 nums[mid] < target 时，说明 mid 落在了 [left, index - 1] 区间上，mid 右边但不包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [mid+ 1, right] 上。因此，更新 left 到 mid + 1 的位置，继续查找。
c. 直到我们的查找区间的⻓度变为 1 ，也就是 left == right 的时候， left 或者right 所在的位置就是我们要找的结果
代码实现

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

4. x的平方根(难度:🔵2度)

oj链接

题目描述

算法原理
设 x 的平方根的最终结果为 index ：
a. 分析 index 左右两次数据的特点：
▪ [0, index] 之间的元素，平方之后都是小于等于 x 的；
▪ [index + 1, x] 之间的元素，平方之后都是大于 x 的。
因此可以使用二分查找算法。
代码实现

class solution {
    public int mysqrt(int x) {
        if (x < 1){
            return 0;
        }
        long left = 1;
        long right = x;
        while(left < right){
            long mid = left + (right - left + 1)/2;//由于是向下取整,所以要加1
            if (mid * mid <= x){
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return (int)left;
    }
}