二分法

二分法概述

    什么是二分法呢？相信大家都有所了解，举个最经典的二分的例子。

​ 给定一个整型有序数组，和一个值$value$，如果$value$在数组中，返回true否则返回false。由于数据状态的特殊性，并不需要遍历数组求解，只需要每次找到数组的中间位置mid，和value相比较，如果$>value$则说明mid位置和mid位置右边的数据都不符合要求，故而更新$r=mid-1$,反之则更新$l=mid+1$。这里给出两套边界条件，请自行筛选。

// 1	
public static boolean exist(int[] arr, int num) {if (sortedArr == null || sortedArr.length == 0) {return false;}int l = 0;int r = arr.length - 1;int mid = 0;// l == r 时结束，剩下最后一个数while (l < 4) { mid = l + ((r - l) >> 1); // 等价于 (l + r) / 2 ,防止溢出if (arr[mid] == num) {return true;} else if (arr[mid] >rnum) {r = mid - 1;} else {l = mid + 1;}}return arr[l] == num;
}

// 2
public static boolean exist(int[] arr, int num) {if (arr == null || arr.length == 0) {return false;}int l = 0;int r = arr.length - 1;int mid = 0;// L == R 时结束，剩下最后一个数while (l < r) {mid = l + ((r - l) >> 1);// 等价于 (l + r) / 2 ,防止溢出if (arr[mid] >= num) {r = mid;} else {l = mid + 1;}}return arr[l] == num;
}

    这个流程并不复杂，难得是边界条件的确定，这个就需要读者自行调试（$Debug$）理解。此处算法的时间复杂度为$O(logN)$，空间复杂度$O(1)$。

二分 >= value最左的位置

    自行完成，这里仅提供参考代码。

    public static int nearLeftIndex(int[] arr, int value) {if (arr == null || arr.length == 0) {return -1;}int l = 0;int r = arr.length - 1;int mid;while (l < r) {mid = (l + r) / 2;if (arr[mid] >= value) {r = mid;} else {l = mid + 1;}}return arr[l] < value ? -1 : l;}

二分 <= value最右的位置

    自行完成，这里仅提供参考代码。

 public static int nearRightIndex(int[] arr, int value) {if (arr == null || arr.length == 0) {return -1;}int l = 0;int r = arr.length - 1;int mid;while (l < r) {mid = l + r + 1 >> 1;if (arr[mid] <= value) {l = mid;} else {r = mid - 1;}}return arr[l] > value ? -1 : l;}

    相信做完这两道题你对二分的理解也更近了一步，那么接下来综合这两道练习题，请完成leetcode32题，这道题是对这两道练习题的综合，可以帮助你更好的掌握二分法，同时二分的写法也有多种，请选择适合自己的边界条件。

局部最小值问题

定义局部最小值：局部最小值是指其值严格小于左右相邻元素的值，给你一个整数数组 nums，找到局部最小值元素并返回其索引。数组可能包含多个局部最小值，在这种情况下，返回 任何一个局部最小值 所在位置即可。

• 你可以认为$nums[-1]=+\infty ，nums[n]=+\infty$

• 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

• $nums[i]!=nums[i+1]$

• $n$为数组长度

    此题由于数据状况特殊，题目局部最小值的定义特殊，所以我们可以使用二分法进行求解。首先我们要先知道$nums[-1]=+\infty ，nums[n]=+\infty$，也就是数组左侧是下降的,并且右侧也是下降(U型)，而且相邻元素之间不相等，这就很特殊了，保证了数组之中一定有局部最小值，并且可以二分。如果$nums[mid]<nums[mid+1]$则左边会存在局部最小值去掉右边（$r=mid$），如果$nums[mid]>nums[mid+1]$则右边会存在局部最小值去掉左边（$l=mid-1$）。

  public static int getLessIndex(int[] arr) {if (arr == null || arr.length == 0) {return -1; // no exist}if (arr.length == 1 || arr[0] < arr[1]) {return 0;}if (arr[arr.length - 1] < arr[arr.length - 2]) {return arr.length - 1;}int l = 1;int r = arr.length - 2;int mid = 0;while (l < r) {mid = l + r >> 1;if (arr[mid] >= arr[mid + 1]) {l = mid + 1;} else {r = mid;}}return l;}

    请完成162. 寻找峰值，如果本篇文章对你有帮助，请点赞、评论、转发，你的支持是我创作的动力！！！