算法 | 二分法
在数据结构书籍中,在介绍二分法时,常常会加上有序这个前提条件,其中有序的定义要麽是从大到小排序,要麽是从小到大排序。
那么,有序真的是所有问题求解时使用二分的必要条件吗?
答案是:不
只要正确构建左右两侧的淘汰逻辑,你就可以使用二分法,那我们现在通过以下例子来了解二分法。
1、在一个有序数组中,找某个数是否存在
2、在一个有序数组中,找>=某个数最左侧的位置
3、在一个有序数组中,找<=某个数最右侧的位置
4、局部最小值问题
在一个有序数组中,找某个数是否存在
public static boolean exist(int[] sortedArr, int num) { if (sortedArr == null || sortedArr.length == 0) { return false; } int L = 0; int R = sortedArr.length - 1; int mid = 0; // L..R 至少两个数的时候 while (L < R) { mid = L + ((R - L) >> 1); if (sortedArr[mid] == num) { return true; } else if (sortedArr[mid] > num) { R = mid - 1; } else { L = mid + 1; } } return sortedArr[L] == num; }
在一个有序数组中,找某个数是否存在.png
在一个有序数组中,找大于等于某个数最左侧的位置
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; }
在一个有序数组中,找大于等于某个数最左侧的位置 .png
在一个有序数组中,找小于等于某个数最右侧的位置
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; }
在一个有序数组中,找小于等于某个数最右侧的位置 .png
局部最小值问题
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 left = 1; int right = arr.length - 2; int mid = 0; while (left < right) { mid = (left + right) / 2; if (arr[mid] > arr[mid - 1]) { right = mid - 1; } else if (arr[mid] > arr[mid + 1]) { left = mid + 1; } else { return mid; } } return left; }
局部最小可以使用二分法完成,定义局部最小时隐含的规律即:一个不存在相同元素的数组一定存在局部最小值,因为只需要找到一个局部最小值,这样就可以使用二分查找将数组规模逐渐减小。
1、首先判断数组第一个值是否小于右边的值,若小于,则局部最小值为第一个数;否则进行下一步;
2、判断数组的最后一个值是否小于左边的值,若小于,则局部最小值为最后一个数;否则进行下一步;
3、通过二分法来验证除首位和末尾位置的数组数据的局部最小值,若某值左右两边的值都大于该值,那么该值就属于局部最小值;否则继续通过二分法进行查找。