Java算法之入门--二分法

说个老生常谈的话题：使用二分法的基础是必须有序数组。但是，不妨设想一下，无序数组能不能也用二分法呢？ 针对这个问题，展开下述研究。在谈这个之前，先聊聊什么是二分法

给出一个数组arr = {1,2,3,4,5,6,7}

要求在数组中找到数字6

正常来说，只要遍历一次数组，逐个数字找一遍即可。

但是，如果是二分法，就不一样了。

在目前阶段来说，二分法一定是建立在有序数组基础上的。这句话是有一定道理。

通常，我们会给出 L M R 三个指针，分别代表左部分，中间值，右部分

对于arr数组来说，(1+7)/2 = 4 所以 M = 4 ;

那么明显的 M = 4 < 6 所以左半部分不用看了，直接令L = M

然后更新M = （4个数）/2 = 5 < 6 再次令 L = M 

依次重复，直到找出数字6

代码如下：

public static boolean find(int[] arr, int num) {
		if (arr == null || arr.length == 0) {
			return false;
		}
		int L = 0;
		int R = arr.length - 1;
		while (L <= R) {
			int mid = (L + R) / 2;
			if (arr[mid] == num) {
				return true;
			} else if (arr[mid] < num) {
				L = mid + 1;
			} else {
				R = mid - 1;
			}
		}
		return false;
	}

给个好玩的题目：

Q：已知arr={1,2,3,4,4,4,5,6,7}在有序数组arr中找到>=4最左的位置

这题直接用二分思想，很快就能解决。代码如下：

public static int mostLeftNoLessNumIndex(int[] arr, int num) {
		if (arr == null || arr.length == 0) {
			return -1;
		}
		int L = 0;
		int R = arr.length - 1;
		int ans = -1;
		while (L <= R) {
			int mid = (L + R) / 2;
			if (arr[mid] >= num) {
				ans = mid;
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		return ans;
	}

说到这里，二分的思想应该有所了解了。但是有一种情况下，即使数组不是无序的，我们仍然能用二分法，但是这里有一个前提。

Q： 无序数组，但相邻下标数不相等，能否找到局部最小值，返回一个即可。

局部最小： 3 a 4 ===》a就是局部最小，理解为函数中的极小值

public static int oneMinIndex(int[] arr) {
		if (arr == null || arr.length == 0) {
			return -1;
		}
		int N = arr.length;
		if (N == 1) {
			return 0;
		}
		if (arr[0] < arr[1]) {
			return 0;
		}
		if (arr[N - 1] < arr[N - 2]) {
			return N - 1;
		}
		int L = 0;
		int R = N - 1;
		// L...R 肯定有局部最小
		while (L < R - 1) {
			int mid = (L + R) / 2;
			if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
				return mid;
			} else {
				if (arr[mid] > arr[mid - 1]) {
					R = mid - 1;
				} else {
					L = mid + 1;
				}
			}
		}
		return arr[L] < arr[R] ? L : R;