二分查找【Lecode_HOT100】

1.搜索插入位置No.35

class Solution {public int searchInsert(int[] nums, int target) {int l = 0;int r = nums.length-1;while(l<=r){int mid = (l+r)>>1;if(nums[mid]==target){return mid;}else if(nums[mid]<target){l = mid+1;}else{r = mid-1;}}return l;}
}

2.搜索二维矩阵No.74

• 方法一：遍历

public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;for(int i = 0;i < m;i++){for (int j = 0;j < n;j++){if(matrix[i][j]==target){return true;}}}return false;}

• 方法二：二分

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;// 定义二分查找的左右边界int left = 0;int right = m * n - 1;while (left <= right) {// 计算中间位置int mid = left + (right - left) / 2;// 将一维索引转换为二维矩阵中的行和列int row = mid / n;int col = mid % n;int midVal = matrix[row][col];if (midVal == target) {return true; // 找到目标值} else if (midVal < target) {left = mid + 1; // 在右半部分查找} else {right = mid - 1; // 在左半部分查找}}return false; // 未找到目标值}
}

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

• 思路：acwing整数二分

 public int[] searchRange(int[] nums, int target) {// 创建返回值数组int[] res = new int[2];res[0] = -1; // 默认值是 -1res[1] = -1; // 默认值是 -1int l = 0;int r = nums.length - 1;// 寻找左边界while (l <= r) {int mid = (l + r + 1) >> 1;if (nums[mid] == target) {res[0] = mid;r = mid-1;  //继续向左搜索} else if (nums[mid] < target) {l = mid + 1;} else {r = mid - 1;}}// 寻找右边界l = 0;r = nums.length - 1;while (l <= r) {int mid = (l + r) >> 1;if (nums[mid] == target) {res[1] = mid;l = mid+1; //继续向右搜索} else if (nums[mid] > target) {r = mid - 1;} else {l = mid + 1;}}return res;}

public int[] searchRange(int[] nums, int target) {int l = 0;int r = nums.length - 1;int[] res = new int[2];res[0] = -1;res[1] = -1;if (nums.length == 0 || nums == null)return res;while (l < r) {int mid = (l + r ) >> 1;if (nums[mid] >= target) {r = mid;} else {l = mid + 1;}}if (nums[l] != target) {return res;} else {res[0] = l;}l = 0;r = nums.length - 1;while (l < r) {int mid = (l + r + 1) >> 1;//+1代表确认右边界if (nums[mid] <= target) {l = mid;} else {r = mid - 1;}}res[1] = l;return res;}

4.搜索旋转排序数组No.33

• 方法一：for循环遍历

public int search(int[] nums, int target) {//for循环遍历for(int i = 0;i<nums.length;i++){if(nums[i]==target){return i;}}return -1;}

• 方法二：二分 O（logN）

public int search(int[] nums, int target) {int l = 0;int r = nums.length-1;while(l<=r){int mid = (l+r)>>1;if(nums[mid]==target){return mid;}if(nums[l]<=nums[mid]){//左半边有序if(nums[l]<=target&&target<=nums[mid]){r = mid-1;}else{l = mid +1;}}else{//右半边有序if(nums[mid]<=target&&target<=nums[r]){l = mid+1;}else{r = mid - 1;}}}return -1;}

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

• 二分
  • 关键在于判断中间值是否大于最右边的值

public int findMin(int[] nums) {int l = 0;int r = nums.length-1;while(l<r){int mid = (l+r)>>1;if(nums[mid]>=nums[r]){//说明小数在右半部分l = mid+1;}else{r = mid;}}return nums[r];}