9.1 搜索插入位置（简单）：二分查找
题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为
O(log n)
的算法。
思想：在一个排序数组中寻求目标值，利用二分法就能正好满足复杂度需求，但该题需要返回不存在数组中值的对应索引，因此需要特殊处理：
- 若插入位置为
pos，则：nums[pos - 1] < target < nums[pos] - 最终left的值就是我们需要求得的应该插入的位置或者就是目标值
总结：要能够清晰的理解题意
代码：
class Solution {
public int searchInsert(int[] nums, int target) {
//设置二分法的左右指针
int left = 0;
int right = nums.length - 1;
//二分查找步骤：左指针小于右指针的情况下循环
while(left <= right){
//中间值的求法
int middle = left + (right - left) / 2;
//左右指针移动
if(nums[middle] < target){
left = middle + 1;
}else{
right = middle - 1;
}
}
//最终索引值就是left；
return left;
}
}
9.2 搜索旋转排序数组(中等)：二分查找
题目：整数数组
nums
按升序排列，数组中的值 互不相同 。
在传递给函数之前，
nums
在预先未知的某个下标
k
（
0 <= k < nums.length
）上进行了 旋转，使数组变为
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
（下标 从 0 开始 计数）。例如，
[0,1,2,4,5,6,7]
在下标
3
处经旋转后可能变为
[4,5,6,7,0,1,2]
。
给你 旋转后 的数组
nums
和一个整数
target
，如果
nums
中存在这个目标值
target
，则返回它的下标，否则返回
-1
。
你必须设计一个时间复杂度为
O(log n)
的算法解决此问题。
思想：原本的数组是升序排列，经过旋转之后，则这道题中给定的数组可以从中心分为两部分，这两部分一定有一部分是有序的，比如:
[4,5,6,7,0,1,2]
，,从
middle
分开为：
[4, 5, 6]
和
[7, 0, 1, 2]
两个部分，其中左边
[4, 5, 6]
这个部分的数组是有序的，然后在使用二分查找
- 由
middle分开为两个部分[l, mid]和[mid + 1, r]，我们查看target位于哪个区间内，然后再在该区间内查找值即可
总结：将旋转后数组从
middle
分为两部分，然后判断
target
的位置
代码：
class Solution {
public int search(int[] nums, int target) {
//若数组为空，直接返回-1
if(nums == null || nums.length == 0){
return -1;
}
//若数组只有一个值，直接判断
if(nums.length == 1){
return target == nums[0] ? 0 : -1;
}
//声明左右指针
int left = 0;
int right = nums.length - 1;
//进行二分查找
while(left <= right){
int middle = left + (right - left) / 2;
if(nums[middle] == target){
return middle;
}
//若目标值在左区间
if(nums[0] <= nums[middle]){
if(nums[0] <= target && target <= nums[middle]){
right = middle - 1;
}else{
left = middle + 1;
}
}//若目标在右区间
else{
if(nums[middle] < target && target <= nums[nums.length - 1]){
left = middle + 1;
}else{
right = middle - 1;
}
}
}
return -1;
}
}
//暴力解法
public int search(int[] nums, int target) {
int i = 0;
for (int num : nums) {
if (num == target) {
return i;
}
i++;
}
return -1;
}
9.3 搜索旋转排序数组Ⅱ（中等）：二分查找
题目：已知存在一个按非降序排列的整数数组
nums
，数组中的值不必互不相同。
在传递给函数之前，
nums
在预先未知的某个下标
k
（
0 <= k < nums.length
）上进行了 旋转 ，使数组变为
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
（下标 从 0 开始 计数）。例如，
[0,1,2,4,4,4,5,6,6,7]
在下标
5
处经旋转后可能变为
[4,5,6,6,7,0,1,2,4,4]
。
给你 旋转后 的数组
nums
和一个整数
target
，请你编写一个函数来判断给定的目标值是否存在于数组中。如果
nums
中存在这个目标值
target
，则返回
true
，否则返回
false
。
你必须尽可能减少整个操作步骤。
思想：不要为了二分查找而进行二分查找，可以存在更优解
总结：要能够清晰的理解题意
代码：
class Solution {
public boolean search(int[] nums, int target) {
for(int v : nums){
if(v == target){
return true;
}
}
return false;
}
}
9.4 搜索二维矩阵（中等）：二分查找
题目：给你一个满足下述两条属性的
m x n
整数矩阵：
- 每行中的整数从左到右按非递减顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数
target
，如果
target
在矩阵中，返回
true
；否则，返回
false
。
思想：将矩阵合并看作为一个升序数组，然后对升序数组进行二分查找
- 我们需要确定的是矩阵中第
(i, j)个位置上是否存在target，因此将每次(i, j)位置的值和target相比较即可，若存在相等值说明就存在 - 我们可以发现：数组第
(i, j)位置的值可以这样取得：nums[middle / n][midlle % n]； - 进行二分查找时，我们直接比较
(i, j)的值和target大小即可，根据大小移动左右指针，可以将此时的(i, j)当作是一个middle
总结：将矩阵合并为一个升序数组后对应索引的位置求法是很巧妙的，可以多在纸上进行数学验证得出
代码：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
//得到数组的长与宽
int m = matrix.length;
int n = matrix[0].length;
//声明矩阵合并为升序数组后的左右指针
int low = 0;
int high = m * n - 1;
//进行二分查找
while(low <= high){
int middle = low + (high - low) / 2;
//矩阵中任意一个元素的值可以表示为：`nums[middle / n][midlle % n]`
int x = matrix[middle / n][middle % n];
//比较当前值和target的大小，若当前值小，由于数组升序，将左指针右移
if(x < target){
low = middle + 1;
}//当前值大，右指针左移
else if(x > target){
high = middle - 1;
}else{
return true;
}
}
return false;
}
}
9.5 寻找旋转排序数组中的最小值（中等）：二分查找（这个有点绕）
题目：已知一个长度为
n
的数组，预先按照升序排列，经由
1
到
n
次 旋转 后，得到输入数组。例如，原数组
nums = [0,1,2,4,5,6,7]
在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组
[a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组
[a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
给你一个元素值 互不相同 的数组
nums
，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为
O(log n)
的算法解决此问题。
思想：一个升序数组经过旋转后，我们可以发现旋转后的数组的最后一个元素
x
和数组的最小值
min
存在一定关系：
min右侧的值一定小于xmin左侧的值一定大于x
通过这一点，运用二分查找可以得出：
- 若
nums[middle] < x，说明最小值在middle的左边，可以直接忽略二分查找的右半区间；注意此时应该为：if(nums[middle] <= nums[high]){ high = middle; }- 因为可能middle值就是目标值，若为high = middle - 1;就少了一个值 - 若
nums[middle] > x，说明最小值在middle的右边，可以直接忽略二分查找的左半区间
总结：注意到舍去左右区间时的操作，可以举特例理解
代码：
class Solution {
public int findMin(int[] nums) {
//声明左右指针
int low = 0;
int high = nums.length - 1;
//进行二分查找
while(low < high){
int middle = low + (high - low) / 2;
//此时，说明最小值位于middle的左边，忽略右边区间
if(nums[middle] <= nums[high]){
high = middle;
}else{
low = middle + 1;
}
}
return nums[low];
}
}
9.6 x的平方根（简单）：二分查找
题目：给你一个非负整数
x
，计算并返回
x
的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)
或者
x ** 0.5
。
思想：只需在小于
x
的范围之内寻找相乘小于等于
x
的最大值即可，使用二分查找
总结：注意
middle * middle
可能会大于
int
的默认范围，需要将其转为
long
代码：
class Solution {
public int mySqrt(int x) {
int low = 0;
int high = x;
int res = 0;
while(low <= high){
int middle = low + (high - low) / 2;
if((long)middle * middle <= x){
res = middle;
low = middle + 1;
}else{
high = middle - 1;
}
}
return res;
}
}
9.7 寻找峰值（中等）：二分查找
题目：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组
nums
，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设
nums[-1] = nums[n] = -∞
。
你必须实现时间复杂度为
O(log n)
的算法来解决此问题。
思想：最大值一定是一个峰值，因此直接寻找最大值即可
总结：最大值一定是峰值，可将该题转换思路进行解决
代码：
class Solution {
public int findPeakElement(int[] nums) {
int low = 0;
int high = nums.length - 1;
while(low < high){
int middle = low + (high - low) / 2;
if(nums[middle] <= nums[middle + 1]){
low = middle + 1;
}else{
high = middle;
}
}
return low;
}
}
9.8 二分法总结！！！
二分法说到底是可能是一个经典的套路框架，但有时候并不容易，当使用二分法求解时，有几点需要极其注意：
- 比较左右指针的大小是
<还是<=，这个要根据题目要求，判断左右边界能否达到相同值 - 左指针
left = middle + 1或者是left = middle：这是左边界问题，我们在使用二分法求解时，要根据情况，判断左边界的left值是否需要留到下一次二分时使用 - 右指针
right= middle - 1或者是right= middle：这是右边界问题，同样需要根据情况判断有边界的值是否需要留到下一次二分时使用
版权归原作者 perseveregz 所有， 如有侵权，请联系我们删除。