【算法题解答·一】二分法

接上文【算法方法总结·一】二分法的一些技巧和注意事项

二分法相关题目如下：

34.在排序数组中查找元素第一和最后一个位置

使用 左闭右闭，[left,right]
关键在于 nums[mid] == target 的部分
找第一个 target 的过程中，如果 nums[mid] == target，说明 mid 已经满足条件，但 mid 前面可能还有相同的 target，把 right 更新为mid - 1，继续往 mid 前找；
找最后一个 target 的过程中，如果 nums[mid] == target，说明 mid 已经满足条件，但 mid 后面可能还有相同的 target，把 left 更新为mid + 1，继续往 mid 后找。

class Solution {public int[] searchRange(int[] nums, int target) {int[] ans = new int[] { -1, -1 }; // 存结果 {第一，最后}int len = nums.length;if (len == 0) return ans;int left = 0, right = len - 1; // 左闭右闭// 找第一个 target，普通的二分查找while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {ans[0] = mid; // 找到后填入ans[0]中right = mid - 1; // 往 mid 前继续找} else if (nums[mid] > target) {right = mid - 1;} else { // nums[mid] < targetleft = mid + 1;}}// 重新初始化left = 0;right = len - 1;// 找最后一个 target，普通的二分查找while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {ans[1] = mid; // 找到后填入ans[1]中left = mid + 1; // 往 mid 后继续找} else if (nums[mid] > target) {right = mid - 1;} else { // nums[mid] < targetleft = mid + 1;}}return ans;}
}

35.搜索插入位置`简单`

使用 左闭右开，[left,right)

class Solution {public int searchInsert(int[] nums, int target) {int n = nums.length;// 左闭右开，[left,right)int l = 0, r = n;while (l < r) {int mid = l + (r - l) / 2;if (target == nums[mid]) {return mid;} else if (target > nums[mid]) {l = mid + 1;} else {r = mid;}}return l; // 如果不知道返回什么，可以自己模拟一下}
}

74.搜索二维矩阵

使用 左闭右开，[left,right)

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;// 有序，所以使用二分搜索，[left,right)int l = 0, r = n * m;while (l < r) {int mid = l + (r - l) / 2;int x = mid / n; // 行索引int y = mid % n; // 列索引if (matrix[x][y] == target) {return true;} else if (matrix[x][y] > target) {r = mid;} else {l = mid + 1;}}return false; // 循环结束还没返回 true，说明没有找到，直接返回 false}
}

33.搜索旋转排序数组

使用 左闭右闭，[left,right]
第一类 2 3 4 5 6 7 | 1 这种，也就是 nums[l] <= nums[mid]。此例子中是 2 <= 5。这种情况下，前半部分有序。如果 nums[l] <= target < nums[mid]，则在前半部分找，否则去后半部分找。
第二类 6 7 | 1 2 3 4 5 这种，也就是 nums[l] > nums[mid]。此例子中就是 6 > 2。这种情况下，后半部分有序。如果 nums[mid] < target <= nums[r]，则在后半部分找，否则去前半部分找。

class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while (l <= r) {int mid = l + (r - l) / 2;if (nums[mid] == target) {return mid;}// 前半段有序，后半段无序if (nums[l] <= nums[mid]) {// target 在前半段if (target >= nums[l] && target < nums[mid]) {r = mid - 1;} else { // target 在后半段l = mid + 1;}} else { // 前半段无序，后半段有序// target 在后半段if (target <= nums[r] && target > nums[mid]) {l = mid + 1;} else { // target 在前半段r = mid - 1;}}}return -1; // 没有找到 target}
}

153.寻找旋转排序数组中的最小值

使用 左闭右开，[left,right)

class Solution {public int findMin(int[] nums) {int l = 0, r = nums.length;while (l < r) {int mid = l + (r - l) / 2;// 断崖最小值在mid右边if (nums[mid] > nums[nums.length - 1]) {l = mid + 1; // 往右半段找} else { // 断崖最小值在mid左边，或为midr = mid; // mid也有可能是最小值}}return nums[l];}
}