1.在一个有序的数组中，查找某一个数是否存在
2.在一个有序的数组中，查找>=2的最左侧位置
3.找到一个局部最小值

在一个有序的数组中，查找某一个数是否存在

找num是否存在 先找一个中间位置 middleIndex middleIndex==num 存在 middleIndex>num 右边一定没有num，可能在左边存在num middleIndex<num 左边一定没有num，可能在右边存在num 如此往复，指导剩下最后一个数没办法再二分

  1. package com.ss.sort;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. /**
  7.  * <p>
  8.  *  在一个有序的数组中，查找某一个数是否存在
  9.  * </P>
  10.  *
  11.  * @author: zhangss
  12.  * @since: 2021-01-05
  13.  **/
  14. public class BinarySearchExist {
  15.     public static boolean exist(int[] arr, int num){
  16.         if(null == arr || arr.length < 1){
  17.             return false;
  18.         }
  19.         if(arr.length == 1 && arr[0] == num){
  20.             return true;
  21.         }
  23.         int l = 0, r = arr.length - 1, mid;
  25.         while (l < r) {
  26.             mid = l + (r - l) / 2;
  27.             if(arr[mid] == num){
  28.                 return true;
  29.             }else if(arr[mid] > num){
  30.                 r = mid - 1;
  31.             }else{
  32.                 l = mid + 1;
  33.             }
  34.         }
  36.         return arr[l] == num;
  37.     }
  39.     public static boolean comparator(int[] arr, int num){
  40.         return exist(arr, num) == Arrays.binarySearch(arr, num) >= 0;
  41.     }
  43.     /**
  44.      * 产生有序数组
  45.      * @return
  46.      */
  47.     public static int[] getSortedArr(){
  48.         Random random = new Random();
  50.         // 若电脑性能有限，生成的数组可以降低长度
  51.         int length = random.nextInt(10);
  52.         int[] arr = new int[length];
  53.         for(int i = 0; i < length; i++){
  54.             arr[i] = random.nextInt(100);
  55.         }
  56.         Arrays.sort(arr);
  57.         return arr;
  58.     }
  60.     public static void main(String[] args) {
  61.         for (int i = 0; i < 50; i++) {
  62.             Random random = new Random();
  63.             int[] arr = getSortedArr();
  64.             int num = random.nextInt(100);
  65.             if(!comparator(arr, num)){
  66.                 System.out.println("第" + (i + 1) + "次");
  67.                 System.out.println(Arrays.toString(arr));
  68.                 System.out.println("num: " + num);
  69.                 System.out.println("失败\n");
  70.             }
  71.         }
  72.     }
  73. }

在一个有序的数组中，查找>=2的最左位置

找num的最左位置 找到中间位置mid， 初始化最左侧位置leftIndex = -1 mid = 2 leftIndex = mid 左边可能有=2的最左位置, 继续找左边 mid > 2 leftIndex = mid 左边可能有=2的最左位置, 继续找左边 mid < 2 右边可能有最左侧位置，继续找右边

  1. package com.ss.sort;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. /**
  7.  * <p>
  8.  * 在一个有序的数组中，查找>=2的最左位置
  9.  * </P>
  10.  *
  11.  * @author: zhangss
  12.  * @since: 2021-01-05
  13.  **/
  14. public class BinarySearchNearLeft {
  15.     public static int nearLeft(int[] arr, int num){
  16.         if(null == arr || arr.length < 1){
  17.             return -1;
  18.         }
  19.         if(arr.length == 1 && arr[0] >= num){
  20.             return 0;
  21.         }
  23.         int l = 0, r = arr.length - 1, mid = 0, leftIndex = -1;
  24.         while (l <= r){
  25.             mid = l + (r - l) / 2;
  26.             if(arr[mid] >= num){
  27.                 leftIndex = mid;
  28.                 r = mid - 1;
  29.             }else{
  30.                 l = mid + 1;
  31.             }
  32.         }
  34.         return leftIndex;
  35.     }
  37.     public static int comparator(int[] arr, int num) {
  38.         int leftIndex = -1;
  39.         for (int i = 0; i < arr.length; i++) {
  40.             if (arr[i] >= num) {
  41.                 leftIndex = i;
  42.                 break;
  43.             }
  44.         }
  45.         return leftIndex;
  46.     }
  48.     /**
  49.      * 产生有序数组
  50.      * @return
  51.      */
  52.     public static int[] getSortedArr(){
  53.         Random random = new Random();
  55.         // 若电脑性能有限，生成的数组可以降低长度
  56.         int length = random.nextInt(5);
  57.         length = length < 2 ? 2 : length;
  58.         int[] arr = new int[length];
  59.         for(int i = 0; i < length; i++){
  60.             arr[i] = random.nextInt(10);
  61.         }
  62.         Arrays.sort(arr);
  63.         return arr;
  64.     }
  66.     public static void main(String[] args) {
  68.         Random random = new Random();
  69.         for (int i = 0; i < 50000; i++) {
  70.             int[] sortedArr = getSortedArr();
  71.             int numIdx = Math.abs(random.nextInt(sortedArr.length - 1));
  72.             int i1 = nearLeft(sortedArr, sortedArr[numIdx]);
  73.             int i2 = comparator(sortedArr, sortedArr[numIdx]);
  74.             if(i1 != i2){
  75.                 System.out.println(Arrays.toString(sortedArr));
  76.                 System.out.println(sortedArr[numIdx]);
  77.                 System.out.println("failed");
  78.             }
  79.         }
  81.     }
  82. }

找到一个局部最小值

局部最小值： 最左边的值小，比右边的值大，就是局部最小值 1.第一个位置上的数。[0]<[1] 就直接是局部最小 2.最后一个位置上的书 [n-1] > [n] 就直接是局部最小 3.[i-1]>[i] && [i+1]>[i] 这样的数就是局部最小值 先判断第一个数、最后一个数是不是局部最小值，是的话就直接找到了，返回该值

minIdx = -1 二分查找，找到中间位置mid [mid] < [mid-1] && [mid] < [mid] + 1 说明这个值就是局部最小，那就不用再找了 [mid-1] < [mid] < [mid + 1] 说明左边必有局部最小 [mid-1] > [mid] > [mid + 1] 说明右边必有局部最小 找到一个就返回

  1. package com.ss.sort;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. /**
  7.  * <p>
  8.  * 找到一个局部最小值
  9.  * </P>
  10.  *
  11.  * @author: zhangss
  12.  * @since: 2021-01-05
  13.  **/
  14. public class BinarySearchAwesome {
  15.     /**
  16.      * 找到一个局部最小值的下标
  17.      * @param arr
  18.      * @return
  19.      */
  20.     public static int getLessIndex(int[] arr){
  21.         if(null == arr || arr.length < 1){
  22.             return -1; // not exist
  23.         }
  24.         if(arr.length > 1 && arr[0] < arr[1]){
  25.             return 0;
  26.         }
  27.         if (arr.length > 1 && arr[arr.length - 1] < arr[arr.length - 2]) {
  28.             return arr.length - 1;
  29.         }
  30.         // 第一个和最后一个都不是局部最小，所以第一个和最后一个都不检查了
  31.         int l = 1, r = arr.length - 2, midIdx = -1;
  32.         while (l <= r){
  33.             midIdx = l + (r - l) / 2;
  34.             if (arr[midIdx] < arr[midIdx + 1]) {
  35.                 r = midIdx - 1;
  36.             } else if (arr[midIdx] > arr[midIdx + 1]) {
  37.                 l = midIdx + 1;
  38.             } else {
  39.                 return midIdx;
  40.             }
  41.         }
  42.         return l;
  43.     }
  45.     /**
  46.      * 生成测试数据
  47.      * 无序，不重复
  48.      * @return
  49.      */
  50.     public static int[] getArr(){
  51.         Random random = new Random();
  52.         int[] arr = {};
  53.         for (int num = 0; num < random.nextInt(100); num++){
  54.             int length = random.nextInt(10);
  55.             length = length > 1 ? length : 2;
  57.             int[] tempArr = new int[length];
  59.             for (int i = 0; i < tempArr.length; i++) {
  60.                 tempArr[i] = random.nextInt(100);
  61.             }
  63.             tempArr = Arrays.stream(tempArr).distinct().sorted().toArray();
  64.             if(random.nextInt(1000)%2 == 0){
  65.                 tempArr = reverse(tempArr);
  66.             }
  68.             arr = Arrays.copyOf(arr, arr.length + tempArr.length);
  69.             for(int i = arr.length - tempArr.length, j = 0; i < arr.length; i++, j++){
  70.                 arr[i] = tempArr[j];
  71.             }
  73.         }
  74.         arr = Arrays.stream(arr).distinct().toArray();
  75.         return arr;
  76.     }
  78.     /**
  79.      * 反转数组
  80.      * @param arr
  81.      * @return
  82.      */
  83.     public static int[] reverse(int[] arr){
  84.         int[] newInt = new int[arr.length];
  85.         for (int i = newInt.length - 1, j = 0 ; i > -1; i--, j++) {
  86.             newInt[j] = arr[i];
  87.         }
  88.         return newInt;
  89.     }
  91.     /**
  92.      * 测试50w次，确认方法没问题
  93.      * @param args
  94.      */
  95.     public static void main(String[] args) {
  96.         for (int i = 0; i < 50_0000; i++) {
  97.             int[] arr = getArr();
  98.             while (arr.length < 2){
  99.                 arr = getArr();
  100.             }
  101.             int lessIndex = getLessIndex(arr);
  103.             if(lessIndex < 0){
  104.                 continue;
  105.             }
  106.             if (lessIndex==0
  107.                     || (lessIndex == (arr.length-1) )
  108.                     || (arr[lessIndex] < arr[lessIndex + 1] && arr[lessIndex] < arr[lessIndex - 1])) {
  109.                 System.out.println("\nok");
  110.             }else{
  111.                 if(lessIndex - 1 >= 0){
  112.                     System.out.print("left: " + arr[lessIndex - 1]);
  113.                 }
  114.                 System.out.print(" less: " + arr[lessIndex]);
  115.                 if (lessIndex + 1 <= arr.length - 1) {
  116.                     System.out.print(" right: " + arr[lessIndex + 1]);
  117.                 }
  118.                 throw new RuntimeException("failed");
  119.             }
  120.         }
  122.     }
  123. }