算法中二分搜索详解

在有序数组中找num是否存在

实现思路

1. 先定义左索引为0，有索引为数组长度-1
2. 然后定义中间索引(在左索引和右索引的中间)
3. 然后拿num和中间索引对应的数作比较，相等的话代表这个数存在。
4. 如果num大于中间索引的数，因为是有序数组，中间索引左边的数都小于等于中间索引的数，所以要查找的数的范围是在中间索引右边到右索引里面，让其左索引等于中间索引加1，然后再从步骤2开始
5. 如果要查找的数小于中间索引的数，那么应该在左索引到中间索引这个范围内，让右索引等于中间索引减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的最左位置

实现思路

1. 先定义左索引为0，有索引为数组长度-1
2. 然后定义中间索引(在左索引和右索引的中间)
3. 定义最终一个索引为-1
4. 判断中间索引的元素和num的比较情况
   1. num大，所以在中间索引右边的区域，重复步骤2
   2. num小，在左边的区域，让最终索引等于中间索引，看左边区域，重复步骤2
5. 返回最终索引
   

代码实现

 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的最右位置

实现思路

1. 和上面第二个的思路差不多。
2. 用暴力解求索引时让其从后往前遍历，然后让其元素小于等于num
3. 在通过最优解(二分查找)时，中间索引大于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. 先判断数组个数
   1. 如果个数为1，那么这个数就是峰值，返回0索引
   2. 如果不为1，也就是大于等于2
2. 数组长度大于等于2
   1. 判断第一个数和第二个数的大小，如果第一个数大于第二个数，那么第一个数就是峰值
   2. 判断倒数第一个数和倒数第二个数，如果倒数第一个数大于倒数第二个数，那么倒数第一个数就是峰值
3. 不属于步骤2的俩个条件，那么就可以用二分搜索
   1. 定义中间索引
   2. 判断中间索引数和中间索引数的前一个数，如果中间索引数小于中间索引数的前一个数，那么中间索引左边的范围必有峰值
   3. 判断中间索引数和中间索引数的后一个数，如果中间索引数小于中间索引数的后一个数，那么中间索引右边的范围必有峰值
   4. 如果上述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;}