目录
一、二分查找简介
运用场景：
- 当数组是有二段性的时候就可以使用，
- 二段性就是指：我们可以找到一个相同规律每次都能够选取一个数，将当前数组分成两段。
- 我们计算中点的时候有两种计算方法，mid = (right + left) / 2 = left + (right - left) / 2 和 mid = (right + left +1) / 2 = left + (right - left +1)。
-
- 这两种方式对于奇数长度的数组来说，没区别，但是对于偶数长度来说，中点有两个点（比如长度为四的数组，中点就可以是1下标也可以是2下标），第一个就是拿到前一个中点，第二个就是拿到后一个中点。
1.1 朴素二分模板
模版：
while(left <= right) {
int mid = left + (right - left) / 2;
if(……) left = mid + 1;
else if(……) right = mid - 1;
else return ……;
}
1.2 查找区间左端点模版
模版：
while(left < right) {
int mid = left + (right - left) / 2;
if(……) left = mid + 1;
else right = mid;
}
1.3 查找区间右端点模版
模版：
while(left < right) {
int mid = left + (right - left + 1) / 2;
if(……) left = mid;
else right = mid - 1;
}
这两个模版详解在目录三的3.1题解中，也就是Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置的题解。
细节理解
- 循环条件left <= right ：这是因为，如果当前[left , right ]区间中只有一个元素的时候，我们还是需要进行比较。
- mid = left + ( right - left) / 2：这是因为，我们直接使用(left + right) / 2来求中间值，如果数组很大那么left + right的值是可能超过int的范围的，减法就没有这种风险。
二、leetcode 704.⼆分查找
题目链接：leetcode 704.⼆分查找
题目描述：
题目解析：
- 这道题就是在一个有序数组中找到一个等于目标值的元素的下标，没找到就返回-1。
2.1 二分查找
解题思路：
- 直接套用上面的朴素模版即可。
解题代码：
//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {
public int search(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) return mid;
else if(nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
}
2.2 暴力枚举
解题思路：
- 直接遍历数组，让目标值与每一个元素相比较，如果相等，那么就返回当前下标。
- 数组遍历完，没找到相等元素，返回-1即可。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public int search(int[] nums, int target) {
for(int i = 0; i < nums.length; i++) {
if(nums[i] == target) return i;
}
return -1;
}
}
三、Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置
题目链接：Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置
题目描述：
题目解析：
- 给的是一个非递减数组，意思就是这个数组中元素的值是一定大于或等于前面一个元素的。
- 返回数组中等于target的子数组的头尾下标，如果只有一个，那么该下标即是头也是尾，如果没有返回两个-1。
- 题目要求使用复杂度为O(logN)，但是其实O(N^2)和O(N)也能过。
3.1 二分查找
解题思路：
- 当我们要找的是一段区间，那么我们可以尝试分别去找左端点和右端点，这样就是一个区间了。
- 我们将数组拆分，可以以等于target来拆分，
-
- 分法一：一段是 >= target的元素，一段是 < target元素，这就是求左端点的分法。
-
- 分法二：一段是 <= target的元素，一段是 > target元素，这就是求右端点的分法。
- 上面两种分法，都是不断按照同一个规律，将数组拆分为两段，这就是二段性的体现。
- 求左端点：
-
- 循环条件：left < right 因为我们是求的左端点，其中并不会写返回语句，当我们left和right相等的时候，我们如果还进循环，就会陷入死循环，并且其实这个时候就是我们要求的左端点了。
-
- 中点的求法：mid = left + (right - left) / 2; 因为当我们只有两个节点时，求取到后一个节点作为中点时，就让mid指向right了，后续更新mid还会指向这里，陷入死循环。
-
- 当mid元素 >= target的时候，因为我们求的是左端点，当前的左端点肯定在[ left , mid]区间之间，并且有可能就是mid，所以要让right指向mid。
-
- 当mid元素 < target 的时候，左端点肯定在( mid , right ] 区间，所有让 left = mid + 1；
- 求右端点：
-
- 循环条件：left < right 因为我们是求的右端点，其中并不会写返回语句，当我们left和right相等的时候，我们如果还进循环，就会陷入死循环，并且其实这个时候就是我们要求的右端点了。
-
- 中点的求法：mid = left + (right - left + 1) / 2; 因为当我们只有两个节点时，以第一个节点为中点，求取到后面就让mid指向left了，后续更新mid还会指向这里，又陷入死循环。
-
- 当mid元素 <= target的时候，因为我们求的是右端点，当前的右端点肯定在[ mid, right ]区间之间，并且有可能就是mid，所以要让left指向mid。
-
- 当mid元素 > target 的时候，右端点肯定在[ left, mid ) 区间，所有让 right = mid - 1；
- 在左右端点求取之间，我们还要更新一下结果中的端点值，如果没找到端点，那么就代表给返回[-1, -1]了。
- 边界：当数组中没有元素的时候，我们去求端点的时候是会直接越界的，所以这种情况要单独处理。
解题代码：
//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[]{-1,-1};
//边界
if(nums.length == 0) return ret;
//查找左端点
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[left] == target) ret[0] = left;
else return ret;
//查找右端点
right = nums.length-1;
while(left < right) {
int mid = left + (right-left+1)/2;
if(nums[mid] > target) right = mid -1;
else left = mid;
}
ret[1] = left;
return ret;
}
}
3.2 暴力枚举
解题思路：
- 我们直接一个for循环，遍历数组，当遇到等于目标值的时候，再一层for循环遍历区间尾即可。
解题代码：
//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[]{-1,-1};
for(int i = 0; i < nums.length; i++) {
if(nums[i] == target) {
ret[0] = i;
for(int j = i; j < nums.length ;j++) {
if(j+1 >= nums.length || nums[j+1] > target) {
ret[1] = j;
return ret;
}
}
}
}
return ret;
}
}
优化：
- 我们可以借助滑动窗口的思想，
- 当我们遇到等于目标值的元素之后，并且left还是初始值的时候，我们就可以将ret[ 0 ]更新。
- 每次right遇到等于目标值的元素的时候，就更新ret[ 1 ]。
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[]{-1,-1};
for(int left = -1,right = 0; right < nums.length; right++) {
if(nums[right] == target) {
ret[1] = right;
if(left == -1) {
left = right;
ret[0] = right;
}
}
if(nums[right] > target) break;
}
return ret;
}
}
四、35.搜索插⼊位置
题目链接：35.搜索插⼊位置
题目描述：
题目解析：
- 数组是升序的，当数组中有等于target，返回该元素下标。
- 如果没有，返回比他小的最近元素的下一个下标。
4.1 二分查找
解题思路：
- 套用上面求左右端点的模版都可以求。
- 有一种边界情况没有求，也就是示例3的情况。单独考虑。
解题代码：
//时间复杂度：O(logN)
//空间复杂度：O(1)
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;
return right+1;
}
}
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 + 1) / 2;
if(nums[mid] > target) right = mid - 1;
else left = mid;
}
if(nums[right] >= target) return right;
return right+1;
}
}
4.2 暴力枚举
解题思路：
- 直接遍历数组。
- 处理边界情况，插入0位置或者插入数组尾。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public int searchInsert(int[] nums, int target) {
for(int i = 0; i < nums.length; i++) {
if(nums[i] == target) return i;
if(nums[i] < target && i < nums.length - 1 && nums[i+1] > target) return i+1;
}
if(nums[0] >= target) return 0;
return nums.length;
}
}
五、69.x的平⽅根
题目链接：69.x的平⽅根
题目描述：
题目解析：
- 求一个数的算术平方根，向下取整。
4.1 二分查找
解题思路：
- 我们可以将 1 - x 的数分为两个区间：小于x算术平方根的区间，大于等于算术平方根的区间。
- 因为我们需要求的是小于等于算术平方根的最大值，所以相当于求右端点。
- 套用模版，处理一下边界情况即可。
- 因为这道题的x范围是整个int，所以当我们求平方的时候是可能超出int范围的，所以我们使用long。
解题代码：
//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {
public int mySqrt(int x) {
long left = 1;
long right = x;
//边界情况
if(x <= 1) return x;
while(left < right) {
long mid = left + (right - left + 1) / 2;
if(mid * mid <= x) left = mid;
else right = mid - 1;
}
return (int)left;
}
}
4.2 暴力枚举
解题思路：直接使用一个for循环，将0 到x 的数遍历，看是否符合要求即可。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public int mySqrt(int x) {
for(long i = 0; i <= x; i++) {
if(i * i == x) return (int)i;
else if(i * i < x && (i+1) * (i+1) > x) return (int)i;
}
return 0;
}
}