算法总结-二分查找
文章目录
- 1.搜索插入位置
- 1.答案
- 2.思路
- 2.搜索二维矩阵
- 1.答案
- 2.思路
- 3.寻找峰值
- 1.答案
- 2.思路
- 4.搜索旋转排序数组
- 1.答案
- 2.思路
- 5.在排序数组中查找元素的第一个和最后一个位置
- 1.答案
- 2.思路
- 6.寻找旋转排序数组中的最小值
- 1.答案
- 2.思路
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指向的元素当做target
if (nums[mid] <= nums[right]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return res;
}
}
2.思路
在二分的基础上，加了一个更新最小值的操作，并且将right指向的元素当做target进行更新左右边界的操作