hot100之二分查找

搜索插入位置(035)

1. class Solution {
2.     public int searchInsert(int[] nums, int target) {
3.         int n = nums.length;
4.         int lef = -1;
5.         int rig = n;
6.         while(lef+1 < rig){
7.             int mid = (lef + rig) / 2;
8.             if (nums[mid] < target){
9.                 lef = mid;
10.             }else rig = mid;
11.         }
12.         return rig;
13.     }
14. }

复制代码

• 分析
  

根本二分
搜索二维矩阵(074)

1. class Solution {
2.     public boolean searchMatrix(int[][] matrix, int target) {
3.         int m = matrix.length;
4.         int n = matrix[0].length;
5.         int lef = -1;
6.         int rig = m*n;
7.         while (lef+1 < rig){
8.             int mid = (lef + rig) / 2;
9.             int x = matrix[mid/n][mid%n];
11.             if (x < target) lef = mid;
12.             else if (x > target) rig = mid;
13.             else return true;
14.         }
15.         return false;
16.     }
17. }

复制代码

• 分析
  

把每一个row 横向相连, 作二分
在排序数组中查找元素的第一个和最后一个位置(034)

1. class Solution {
2.     public int[] searchRange(int[] nums, int target) {
3.         
4.         int start = searchLower(-1 ,nums, target);
5.         if (start == nums.length || nums[start] != target) return new int[]{-1,-1};
7.         int end = searchLower(start, nums, target+1) -1;
8.         return new int[] {start, end};
9.     }
11.     private int searchLower(int lef, int[] nums, int target){
13.         int rig = nums.length;
15.         while (lef + 1 < rig){
16.             int mid = (lef + rig) / 2;
17.             if (nums[mid] < target) lef = mid;
18.             else rig = mid;
19.         }
21.         return rig;
22.     }
23. }

复制代码

• 分析
  

通过两次二分 查找 target 和target+1的起始位置, 确定target的范围
搜索旋转排序数组(033)

1. class Solution {
2.     public int search(int[] nums, int target) {
3.         int n = nums.length -1;
4.         int lef = -1;
5.         int rig = n;
6.         while (lef + 1< rig){
7.             int mid = (lef + rig) / 2;
8.             if (check(nums, target, mid)){       //target在mid右侧
9.                 lef = mid;
10.             }else rig = mid;
11.         }
12.         return nums[rig] == target ? rig : -1;
13.     }
15.     private boolean check(int[] nums, int target, int idx){   
16.         int x = nums[idx];
17.         int end = nums[nums.length-1];
19.         if (x < end){
20.             return x < target && target <= end;  // mid在小端 且比target小
21.         }
22.         // mid在大端 且< target在小端 || target > mid >
23.         return x < target || target <= end;
24.     }
25. }

复制代码

• 分析
  

判断 mid 在 →

• 感悟
  

二分用来查找数据的拐点,  以作check()
寻找两个正序数组的中位数(004)

这题给我写晕厥了😣😣

1. class Solution {
2.     public int findMin(int[] nums) {
3.         int n = nums.length;
4.         int lef = -1;
5.         int rig = n;
6.         while (lef+1 < rig){
7.             int mid = (lef + rig) / 2;
8.             if(nums[mid] > nums[n-1]){   // 在右侧
9.                 lef = mid;
10.             }else rig = mid;
11.         }
12.         return nums[rig];
13.     }
14. }

复制代码

• 分析
  

我们取两数组作为总数据集的小端, 作为总数据集的大端

💡假设在全落在第一组
从取出值放入
从取出值放入
直到全落在第二组
我们可以看到, 的sum是先变小, 再变大, 显然我们可以观察到拐点, 即为sum最小值,也是我们要找的数据集小端

接下来我们通过二分找拐点if(nums1[mid_nums1] - nums2[mid_nums2+1]