基础算法之二分查找--Java实现(下)--LeetCode题解:山脉数组的峰顶索引-寻找峰值-寻找旋转排序数组中的最小值-点名
这里是Themberfue
山脉数组的峰顶索引
题目解析
如图所见，该数组是一个先递增后递减的数组，那么它肯定有一个最大值，找到这个最大值，返回其索引即可。
算法讲解
· 这题的数组不是单调的啊？也可以用二分吗？
· 二分查找不一定就一定要数组有序，只要满足二段性即可。
· 我们发现，最大值左边的数字，前一个元素一定小于后一个元素，而最大值右边的数字，前一个元素一定大于后一个元素。
· 这便发现了二段性，我们便可以利用这一性质使用二分查找。
· 若是 mid 的前一个元素小于 mid，那么 mid落在左边这一段，所以答案在右边，但是 mid可能就是答案，所以 left = mid
· 若是 mid的前一个元素大于 mid，那么 mid落在右边这一段，所以答案在左边，所以 right = mid - 1
编写代码
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 1, right = arr.length - 2;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (arr[mid] > arr[mid - 1]) left = mid;
else right = mid - 1;
}
return left;
}
}寻找峰值
题目解析
这题可以说是上一题的延伸版，就是这个数组不止有一个峰顶，有多个峰顶，返回一个即可。
算法讲解
· 这题既然只需找到一个即可，那么我们只盯着一个看即可。
· 所以这题也就变成了和上题一样的思路。
· 其实代码也一样
编写代码
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
}class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] > nums[mid - 1]) left = mid;
else right = mid - 1;
}
return left;
}
}寻找旋转排序数组中的最小值
题目解析
旋转数组也就是将数组最后一个数头插，旋转一次头插一次，以此类推，找到最小值即可。
算法讲解
· 这题如果没有时间复杂度限制的话，一行代码即可搞定。但是既然规定了时间复杂度，那就最好按这个写，不然就是 "回家等消息了" 🤡。它既然规定了时间复杂度为 logN，基本上就是二分查找了。
· 这个数组的二段性体现在哪呢？我们画图来看看。
· 相信你已经看出二段性了。
· 现在我们应该选取一个基准值来和 mid 进行比较了，那么选择哪个呢？我建议是选择右边的，如果选左边的话，还需要考虑特殊情况（数组完全升序的情况）。
· 既然我们选择了右边作为基准值pivot，如果 mid 所对应的元素小于 pivot的话，说明它在右边这一段，又因为 mid 可能就是答案，所以 right = mid。
· 如果 mid 对应的元素大于 pivot的话，说明它在左边这一段，所以 left = mid + 1。
· 我还会提供一个以左边为基准值的代码，以供参考。
编写代码
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
int x = nums[right];
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > x) left = mid + 1;
else right = mid;
}
return nums[left];
}
}class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
int x = nums[left]; // 以最左边的元素作为基准值
// 处理特殊情况
if (nums[0] < nums[nums.length - 1]) return nums[0];
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < x) {
right = mid; // 最小值在左边，包括mid
} else {
left = mid + 1; // 最小值在右边
}
}
return nums[left]; // 最终返回找到的最小值
}
}点名
题目解析
数组中是严格依此递增的，但是缺少了一个元素，找出那个元素即可
算法讲解
· 这题其实又多种解法的 => 高斯求和，暴力遍历，位运算，哈希，二分查找
· 但今天的主角的是二分查找，所以我们之讲二分这一个方法。
· 我们想找其二段性，提供画图我们可以看到。
· 相信你已经看出来了，这个数组的二段性就是下标和下标对应的元素相同以及下标和小标对应的元素不相同。
· 多说不义必自毙，所以我就直接贴代码了
编写代码
class Solution {
public int takeAttendance(int[] records) {
int left = 0, right = records.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (records[mid] == mid) left = mid + 1;
else right = mid;
}
return records[left] == left ? left + 1 : left;
}
}好了，以上就是今天内容的全部讲解，如果有不懂的地方，随时私聊😘
我们下一章节 => 前缀和见😁
原文地址：https://blog.csdn.net/Themberfue/article/details/142712223
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！