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

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

---

二分法相关题目如下： 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] < target left = 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] < target left = 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左边，或为mid r = mid; // mid也有可能是最小值 } } return nums[l]; } }

---

4.寻找两个正序数组的中位数困难

暴力法很简单，但是二分法很有难度，先挖个坑之后填