算法中二分搜索详解
文章目录
在有序数组中找num是否存在
实现思路
- 先定义左索引为0，有索引为数组长度-1
- 然后定义中间索引(在左索引和右索引的中间)
- 然后拿num和中间索引对应的数作比较，相等的话代表这个数存在。
- 如果num大于中间索引的数，因为是有序数组，中间索引左边的数都小于等于中间索引的数，所以要查找的数的范围是在中间索引右边到右索引里面，让其左索引等于中间索引加1，然后再从步骤2开始
- 如果要查找的数小于中间索引的数，那么应该在左索引到中间索引这个范围内，让右索引等于中间索引减1，再从步骤2开始
实现代码(里面运用了对数器)
public static void main(String[] args) {
int N = 100;
int V = 1000;
int testTime = 500000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
//[0,1) * 100 <=> [0,100)
int n = (int) (Math.random() * N);
int[] arr = randomArray(n, V);
Arrays.sort(arr);
int num = (int) (Math.random() * V);
int a = right(arr,num);
int b = getIndex(arr,num);
if (a != b){
System.out.println("出错了！");
}
}
System.out.println("测试结束");
}
public static int right(int[] arr, int num) {
if (Arrays.binarySearch(arr, num) >= 0){
return Arrays.binarySearch(arr, num) ;
}else {
return -1;
}
}
public static int getIndex(int[] arr, int num) {
if (arr == null || arr.length == 0) {
return -1;
}
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == num) {
return mid;
} else if (arr[mid] > num) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
public static int[] randomArray(int n, int v) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
//[0,1) * 1000 + 1 <=> [1,1000]
arr[i] = (int) (Math.random() * v) + 1;
}
return arr;
}
在有序数组中找>=num的最左位置
实现思路
- 先定义左索引为0，有索引为数组长度-1
- 然后定义中间索引(在左索引和右索引的中间)
- 定义最终一个索引为-1
- 判断中间索引的元素和num的比较情况
- num大，所以在中间索引右边的区域，重复步骤2
- num小，在左边的区域，让最终索引等于中间索引，看左边区域，重复步骤2
- 返回最终索引
代码实现
public static void main(String[] args) {
int N = 100;
int V = 1000;
int testTime = 500000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int n = (int) (Math.random() * N);
int[] arr = randomArray(n, V);
Arrays.sort(arr);
int num = (int) Math.random() * V;
if (rightIndex(arr,num) != getIndex(arr,num)){
System.out.println("出错了！");
}
}
System.out.println("测试结束");
}
public static int[] randomArray(int n, int v) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * v + 1);
}
return arr;
}
public static int rightIndex(int[] arr, int num) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= num) {
return i;
}
}
return -1;
}
public static int getIndex(int[] arr, int num) {
int left = 0;
int right = arr.length - 1;
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < num){
left = mid + 1;
}else {
ans = mid;
right = mid -1;
}
}
return ans;
}
在有序数组中找<=num的最右位置
实现思路
- 和上面第二个的思路差不多。
- 用暴力解求索引时让其从后往前遍历，然后让其元素小于等于num
- 在通过最优解(二分查找)时，中间索引大于num时，范围就编程中间索引的左边；反之最终索引等于中间索引，然后范围在中间索引的右边
实现代码
public static void main(String[] args) {
int N = 100;
int V = 1000;
int testTime = 500000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int n = (int) (Math.random() * N);
int[] arr = randomArray(n, V);
Arrays.sort(arr);
int num = (int) Math.random() * V;
if (rightIndex(arr,num) != getIndex(arr,num)){
System.out.println("出错了！");
}
}
System.out.println("测试结束");
}
public static int[] randomArray(int n, int v) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * v + 1);
}
return arr;
}
public static int rightIndex(int[] arr, int num) {
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] <= num) {
return i;
}
}
return -1;
}
public static int getIndex(int[] arr, int num) {
int left = 0;
int right = arr.length - 1;
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > num){
right = mid - 1;
}else {
ans = mid;
left = mid + 1;
}
}
return ans;
}
二分搜索不一定发生在有序数组上(比如寻找峰值问题)
题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 arr，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 arr[-1] = arr[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
实现思路
- 先判断数组个数
- 如果个数为1，那么这个数就是峰值，返回0索引
- 如果不为1，也就是大于等于2
- 数组长度大于等于2
- 判断第一个数和第二个数的大小，如果第一个数大于第二个数，那么第一个数就是峰值
- 判断倒数第一个数和倒数第二个数，如果倒数第一个数大于倒数第二个数，那么倒数第一个数就是峰值
- 不属于步骤2的俩个条件，那么就可以用二分搜索
- 定义中间索引
- 判断中间索引数和中间索引数的前一个数，如果中间索引数小于中间索引数的前一个数，那么中间索引左边的范围必有峰值
- 判断中间索引数和中间索引数的后一个数，如果中间索引数小于中间索引数的后一个数，那么中间索引右边的范围必有峰值
- 如果上述bc都不成立，那么中间索引数为峰值
实现代码
public int findPeakPoint(int[] arr) {
int n = arr.length;
if (arr == null || arr.length == 0) {
return -1;
}
if (arr.length == 1) {
return 0;
}
if (arr[0] > arr[1]) {
return 0;
}
if (arr[n - 1] > arr[n - 2]) {
return n - 1;
}
int left = 1;
int right = n - 2;
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid - 1] > arr[mid]) {
right = mid - 1;
} else if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
ans = mid;
break;
}
}
return ans;
}
原文地址：https://blog.csdn.net/m0_69266818/article/details/137717671
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！