当前位置：首页 > news >正文

2023.3.21

news 2025/8/13 15:01:43

6：有序数组中找到num

// arr保证有序，在arr数组中寻找num，二分查找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;}

7：有序数组中找到>=num最左的位置

在这里插入图片描述

首先通过二分查找找到的是mid == 5位置的数，arr【5】 >= 2 ,符合条件，让T记录一下这个位置，T = 5；

然后再去左边寻找，看看有没有arr>=2并且下标比5小的位置,如果有就让T记录一下这个位置，将最后的T的结

果返回。

	// 有序数组中找到>=num最左的位置// 1 2 2 3 4 5 6 7  数组// 0 1 2 3 4 5 6 7 下标// num == 2  return 1public static int mostLeftNoLessNumIndex(int[] arr, int num) {if(arr == null || arr.length == 1) {return -1;}int L = 0;int R = arr.length - 1;// ans:是用来计数的，用来记录>=num的位置int t = -1;while(L <= R) {int mid = (L + R) / 2;if(arr[mid] >= num) {t = mid;R = mid - 1;}else {L = mid + 1;}}return t;}

8：有序数组中找到<=num最右的位置

	// 有序数组中找到<=num最右的位置// 1 2 2 3 4 5 6 7  数组// 0 1 2 3 4 5 6 7 下标// num <= 2  return 2public static int nearestIndex(int[] arr, int value) {if(arr == null || arr.length == 1) {return -1;}int L = 0;int R = arr.length - 1;// ans:是用来计数的，用来记录>=num的位置int t = -1;while(L <= R) {int mid = (L + R) / 2;if(arr[mid] <= value) {t = mid;L = mid + 1;}else {R = mid - 1;}}return t;}

9：局部最小值问题

在这里插入图片描述

自写：

	// arr 相邻的数不相等！ 返回一个局部最小的下标public static int oneMinIndex(int[] arr) {if(arr == null || arr.length == 0) {return -1;}if(arr.length == 1) {return 0;}int L = 0;int R = arr.length - 1;if(arr[L] < arr[L + 1]) {return L;}if(arr[R] < arr[R - 1]) {return R;}// 之后是两边下陷的情况while(L <= R) {int mid = (L + R) / 2;if (mid -1 >= L && mid +1 <= R && arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {return mid;}if(mid -1 >= L && arr[mid] > arr[mid - 1]) {R = mid - 1;continue;}if(mid +1 <= R && arr[mid] > arr[mid + 1]) {L = mid + 1;}// L与R相邻的时候，直接返回最小的那个if(mid == L || mid == R) {return arr[L] > arr[R] ? R : L;}}return -1;}

左神：

// arr 相邻的数不相等！ 返回一个局部最小的下标public static int oneMinIndex2(int[] arr) {if(arr == null || arr.length == 0) {return -1;}if(arr.length == 1) {return 0;}int L = 0;int R = arr.length - 1;if(arr[L] < arr[L + 1]) {return L;}if(arr[R] < arr[R - 1]) {return R;}// 之后是两边下陷的情况while(L < R-1) {int mid = (L + R) / 2;if (arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {return mid;}if(arr[mid] > arr[mid - 1]) {R = mid - 1;continue;}if(arr[mid] > arr[mid + 1]) {L = mid + 1;}}return arr[L] < arr[R] ? L : R;}

在这里插入图片描述

总结一下：

	public static int oneMinIndex3(int[] arr) {if (arr == null || arr.length == 0) {return -1;}int N = arr.length;if (N == 1) {return 0;}//到这，arr的长度是大于等于2的if (arr[0] < arr[1]) {return 0;}if (arr[N - 1] < arr[N - 2]) {return N - 1;}int L = 0;int R = N - 1;int ans = -1;while (L <= R) {int mid = (L + R) / 2;//中间位置是否是最小，[mid-1] > [mid] < [mid+1]if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {ans = mid;break;//不同时小，下面两个判断选一个就行} else if (arr[mid] > arr[mid - 1]) {R = mid;} else {//arr[mid] > arr[mid + 1]L = mid;}}return ans;}
}

L == 0 ，R == n - 1

0 与 n - 1位置上一定不是局部最小值，而 [ 1 , n-2 ] 之间一定有局部最小值，所以 mid (mid：锁定局部最小

值的)不可能来到下标 0 与 n - 1 的位置，下标 0 与 n - 1 作为一个缓冲区（如果来到0或n-1的旁边，0与n - 1

可作为一个缓冲区，就不会出现mid-1或者mid+1越界的情况）。如果mid位置是局部最小值就返回了，如果没

返回说明mid位置不是局部最小值，我们就令L == mid 或者是 R == mid，这样 L 与 R 也是一个缓冲区，L与R

之间一定有局部最小值。还有就是，不会有(L == 0&& R == 1 ) || (L == N-2 && R == N-1 )

的情况，如果出现上述的情况说明一定没有局部最小值（L与R是缓冲区，中间没有值），然而事实是一定有

局部最小值。

这个方法的关键是：下标0，N-1的区域做缓冲区，L与R做缓冲区。所以没有越界的风险。

	public static int getLessIndex(int[] arr) {if (arr == null || arr.length == 0) {return -1;}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谁都是对的，因为一定有区域最小值return left; }

L == 1 ，R == n - 2

如果mid位置是局部最小值就返回了，如果没返回说明mid位置不是局部最小值，我们就

令L == mid + 1 或者是 R == mid - 1，mid一定不是局部最小值，但是mid+1与mid-1可能是局部最小值。所以

【L，R】L与R之间都是 “好的” 都是有可能是局部最小值的区域，剔除不是局部最小值的部分，在是局部最小

值的区域寻找。

这个方法的关键：[L , R] L与R之间都是“好的”部分（可能是局部最小值的部分）不可能来到下标 0，n - 1位

置，并且下标 0，n - 1位置可以作为一个缓冲，所以不会出现越界的状况。

// arr 相邻的数不相等！ 返回一个局部最小的下标public static int oneMinIndex(int[] arr) {if(arr == null || arr.length == 0) {return -1;}if(arr.length == 1) {return 0;}int L = 0;int R = arr.length - 1;if(arr[L] < arr[L + 1]) {return L;}if(arr[R] < arr[R - 1]) {return R;}// 之后是两边下陷的情况while(L <= R) {int mid = (L + R) / 2;if (mid -1 >= L && mid +1 <= R && arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {return mid;}if(mid -1 >= L && arr[mid] > arr[mid - 1]) {R = mid - 1;continue;}if(mid +1 <= R && arr[mid] > arr[mid + 1]) {L = mid + 1;}// L与R相邻的时候，直接返回最小的那个if(mid == L || mid == R) {return arr[L] > arr[R] ? R : L;}}return -1;}