当前位置：首页
> .html
导读：在数据结构书籍中，在介绍二分法时，常常会加上有序这个前提条件，其中有序的定义要麽是从大到小排序，要麽是从小到大排序。
那么，有序真的是所有问题求解时使用二分的必要条件吗？
答案是：...
在数据结构书籍中，在介绍二分法时，常常会加上有序这个前提条件，其中有序的定义要麽是从大到小排序，要麽是从小到大排序。
那么，有序真的是所有问题求解时使用二分的必要条件吗？
答案是：不
只要正确构建左右两侧的淘汰逻辑，你就可以使用二分法，那我们现在通过以下例子来了解二分法。
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、通过二分法来验证除首位和末尾位置的数组数据的局部最小值，若某值左右两边的值都大于该值，那么该值就属于局部最小值；否则继续通过二分法进行查找。
相关文章
发表评论: