Algorithm-Day03

前言

如果想成为别人口中的大佬，那就无时无刻的卷，追随着大佬的步伐......

二分法用法

有序数组中找到Num

// 返回找到数值的索引，没找到返回-1
public static int FindValue(int[] arr, int value){
//数组为空 则返回-1
if (arr == null || arr.length == 0) {
return -1;
}
int L = 0;
int R = arr.length - 1;
int index = -1;
while (L <= R) {
int mid = (L + R) / 2; //对半查找
if (arr[mid] == num) {
return mid;
} else if (arr[mid] < num) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return index;
}

找到大于等于一个Num最左的位置

// 思路：二分查找，找到中间值直接进行比较，缩小范围，记录索引，继续比较，
public static nearNumIndex(int[] arr, int value){
if (arr == null || arr.length == 0) {
return -1;
}
int L = 0;
int R = arr.length -1;
int index = -1;
while(L <= R){
int mid = (L + R) / 2;
if (arr[mid] >= value) {
R = mid - 1;
// 如果找到了一个符合条件的值，就记录，并且继续向左寻找还有没有符合条件的
ans = mid;
}else {
L = mid + 1;
}
}
}
// 最右边位置 同理

局部最小问题

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;
}