算法基础（二）- 二分查找
基础练习
题目要求：在一个有序数组中找到要求的某个值，若不存在，返回-1
话不多说，直接上代码：
private static int exist(int[] sortedArr, int num) {
if (sortedArr == null || sortedArr.length == 0) {
return -1;
}
int left = 0;
int right = sortedArr.length - 1;
int mid;
while (left < right) {
mid = left + ((right - left) >> 1);
if (sortedArr[mid] == num) {
return mid;
}
if (sortedArr[mid] > num) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return sortedArr[left] == num ? left : -1;
}
基础升级
题目要求1：在一个有序数组中，找大于等于某个数最左侧的位置
本题是上个题目的简单变形。在原来的基础之上，只需额外记录每次迭代过程中，符合要求的上一条记录，直到不符合条件为止即可。
public static int nearestIndex(int[] arr, int value) {
int L = 0;
int R = arr.length - 1;
int index = -1;
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (arr[mid] >= value) {
index = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
return index;
}
题目要求2：在一个有序数组中，找小于等于某个数最右侧的位置
public static int nearestIndex(int[] arr, int value) {
int L = 0;
int R = arr.length - 1;
int index = -1;
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (arr[mid] <= value) {
index = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
return index;
}
寻找峰值
题目来源：https://leetcode-cn.com/problems/find-peak-element/
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
示例 1：
输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。示例 2：
输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。
解题思路：注意给出的数组不是有序的，但我们仍然可以应用二分法来解决这个问题：
1.首先检查开头元素是否符合要求--即 if (nums[0] > nums[1]) return 0;2.然后检查末位元素是否符合要求--即 if (nums[nums.length-1] > nums[nums.length-2]) return nums.length-1;3.若以上两条都不满足，那么可以推断出中间元素必定存在峰值情况。0号元素 < 1号元素 nums.length-1 元素 < nums.length-2 元素 存在如下图，数组显示呈上升趋势、最后是下降趋势，因此中间一定存在拐点，即我们所要求的峰值！
如何查找中间情况的峰值呢？我们可以使用二分法：
1.先取中间元素下标 mid，如果 nums[mid] > nums[mid-1] 且 nums[mid] > nums[mid+1] ，直接返回；2.若 nums[mid] < nums[mid+1] ，则为趋势上升，左指针右移至mid+1；否则为趋势下降，右指针左移至 mid-1。
代码实现如下：
public static int findPeakElement(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
if (arr.length == 1 || arr[0] > arr[1]) {
return 0;
}
if (arr[arr.length - 1] > arr[arr.length - 2]) {
return arr.length - 1;
}
int left = 1;
int right = arr.length - 2;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (arr[mid] < arr[mid - 1]) {
right = mid - 1;
} else if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
小结
二分法不只可以用于有序数组的情况，只要是对所求问题能够一分为二，构建左右两侧的淘汰逻辑，就可以使用二分。
题图：Photo by Sharon McCutcheon on Unsplash