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

🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:
🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm=1001.2014.3001.5482
🍕 Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(96平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
🍃 Spring(97平均质量分)https://blog.csdn.net/2301_80050796/category_12724152.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~

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

OJ链接

• 题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -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;}
}

[注意事项]

1. 计算mid的时候,没有使用(left+right)/2,而是使用left+(right-left)/2的形式.
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链接

• 题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

• 算法原理
  方便叙述，用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链接

• 题目解析

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

• 算法原理
  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 ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

• 算法原理
  设 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;//由于是向下取整,所以要加1if (mid * mid <= x){left = mid;}else{right = mid - 1;}}return (int)left;}
}

[注意] 我们这里使用long,防止数据溢出.