算法总结-二分查找

1.搜索插入位置

1.答案

package com.sunxiansheng.arithmetic.day18;/*** Description: 35. 搜索插入位置** @Author sun* @Create 2025/1/30 10:11* @Version 1.0*/
public class t35 {public static int searchInsert(int[] nums, int target) {// 左闭右闭，加等号int left = 0, right = nums.length - 1;while (left <= right) {// 求中点int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;}if (nums[mid] < target) {left = mid + 1;}if (nums[mid] > target) {right = mid - 1;}}// 如果找不到，就返回应该插入的位置return left;}
}

2.思路

左闭右闭，加等号，求中点，找不到就返回left

2.搜索二维矩阵

1.答案

package com.sunxiansheng.arithmetic.day18;/*** Description: 74. 搜索二维矩阵** @Author sun* @Create 2025/1/30 10:16* @Version 1.0*/
public class t74 {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;// 左闭右闭int left = 0, right = m * n - 1;// 加等号while (left <= right) {// 求中点int mid = left + (right - left) / 2;// 转换中点下标为二维数组的下标int i = mid / n;int j = mid % n;if (matrix[i][j] == target) {return true;}if (matrix[i][j] < target) {left = mid + 1;}else if (matrix[i][j] > target) {right = mid - 1;}}return false;}
}

2.思路

就是在求中点的时候有些不一样，需要将数字转换为二维数组的下标，公式就是x / n 和 x % n

3.寻找峰值

1.答案

package com.sunxiansheng.arithmetic.day18;/*** Description: 162. 寻找峰值** @Author sun* @Create 2025/1/30 10:35* @Version 1.0*/
public class t162 {public int findPeakElement(int[] nums) {// 左闭右闭加等号int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;// 判断是否大于左右边元素boolean leftSmaller = mid == 0 || nums[mid] > nums[mid - 1];boolean rightSmaller = (mid == nums.length - 1) || nums[mid] > nums[mid + 1];// 如果都大于，则当前元素就是峰值if (leftSmaller && rightSmaller) {return mid;}// 如果比左边的元素大，则峰值在右边if (leftSmaller) {left = mid + 1;} else {// 其余情况峰值在左边right = mid - 1;}}return -1;}
}

2.思路

除了二分老套路之外，还要判断是否大于左右边元素，如果都大于就是峰值，如果只是大于左边但是小于右边，那么峰值就在右边

4.搜索旋转排序数组

1.答案

package com.sunxiansheng.arithmetic.day18;/*** Description: 33. 搜索旋转排序数组** @Author sun* @Create 2025/1/30 11:05* @Version 1.0*/
public class t33 {public static int search(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}// 左闭，右闭，加等号int left = 0, right = nums.length - 1;while (left <= right) {// 求中点int mid = left + (right - left) / 2;// 找到了就直接返回if (target == nums[mid]) {return mid;}// 找不到，如果左边是有序的if (nums[mid] >= nums[left]) {// 判断是否在左边if (target >= nums[left] && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else {// 目前是右边有序，则判断是否在右边if (target <= nums[right] && target > nums[mid]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}
}

2.思路

左闭右闭加等号，求中点，如果找不到，就判断左边是不是有序的，如果左边有序，就进一步判断元素是否在左边，如果在就right = mid - 1，否则就是left = mid + 1，右边也是同理

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

1.答案

package com.sunxiansheng.arithmetic.day18;/*** Description: 34. 在排序数组中查找元素的第一个和最后一个位置** @Author sun* @Create 2025/1/30 11:23* @Version 1.0*/
public class t34 {public int[] searchRange(int[] nums, int target) {if (nums == null || nums.length == 0) {return new int[]{-1, -1};}return new int[]{getFirst(nums, target), getLast(nums, target)};}private int getFirst(int[] nums, int target) {// 左闭右闭，加等号int left = 0, right = nums.length - 1;while (left <= right) {// 求中点int mid = left + (right - left) / 2;if (target <= nums[mid]) {right = mid - 1;} else {left = mid + 1;}}// 防止越界if (left < 0 || left > nums.length - 1) {return -1;}return nums[left] == target ? left : -1;}private int getLast(int[] nums, int target) {// 左闭右闭，加等号int left = 0, right = nums.length - 1;while (left <= right) {// 求中点int mid = left + (right - left) / 2;if (target >= nums[mid]) {left = mid + 1;} else {right = mid - 1;}}// 防止越界if (right < 0 || right > nums.length - 1) {return -1;}return nums[right] == target ? right : -1;}
}

2.思路

以找到第一个元素为例，首先还是二分老套路，然后如果target小于等于mid的元素，就在左边，否则在右边，注意退出循环后要防止越界，并且最后返回的时候也要判断left下的元素是不是那个元素！

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

1.答案

package com.sunxiansheng.arithmetic.day18;/*** Description: 153. 寻找旋转排序数组中的最小值** @Author sun* @Create 2025/1/30 13:07* @Version 1.0*/
public class t153 {public int findMin(int[] nums) {// 左闭右闭加等号int left = 0, right = nums.length - 1;int res = nums[left];while (left <= right) {// 求中点int mid = left + (right - left) / 2;// 更新最小值res = Math.min(res, nums[mid]);// 将right指向的元素当做targetif (nums[mid] <= nums[right]) {right = mid - 1;} else  {left = mid + 1;}}return res;}
}

2.思路

在二分的基础上，加了一个更新最小值的操作，并且将right指向的元素当做target进行更新左右边界的操作