有序数组中找到给定的num

每次都取中点数与num比较 如果中点数比num小，则左边界来到中点数+1的位置，将右侧部分再进行二分 如果中点数比num大，则右边界来到中点数-1的位置，将左侧部分在进行二分

  1. public static boolean exist(int[] arr, int num) {
  2.     if (arr == null || arr.length == 0) {
  3.         return false;
  4.     }
  5.     int l = 0;
  6.     int r = arr.length - 1;
  7.     int mid = 0;
  8.     while (l < r) {
  9.         mid = l + ((r - l) >> 2);
  10.         if (arr[mid] == num) {
  11.             return true;
  12.         }
  13.         if (arr[mid] > num) {
  14.             r = mid - 1;
  15.         } else if (arr[mid] < num) {
  16.             l = mid + 1;
  17.         }
  18.     }
  19.     return arr[l] == num;
  20. }

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

二分法找相等的数题目变种，只要有>=num的数据，就记录下标，且右边界 = 二分索 - 1，直到二分全部执行完毕返回记录的下标位置

  1. public int nearestIndex(int[] arr, int number) {
  2.     if (arr == null || arr.length == 0) {
  3.         return -1;
  4.     }
  5.     int l = 0;
  6.     int r = arr.length - 1;
  7.     int mid = 0;
  8.     int index = -1;
  9.     while (l < r) {
  10.         mid = l + ((r - l) >> 2);
  11.         if (arr[mid] >= number) {
  12.             r = mid - 1;
  13.             index = mid;
  14.         } else {
  15.             l = mid + 1;
  16.         }
  17.     }
  18.     return arr[l] >= number ? l : index;
  19. }

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

二分法找相等的数题目变种，只要有<=num的数据，就记录下标，且左边界 = 二分索引 + 1，直到二分全部执行完毕返回记录的下标位置

  1. public static int nearestIndex(int[] arr, int number) {
  2.     if (arr == null || arr.length == 0) {
  3.         return -1;
  4.     }
  5.     int l = 0;
  6.     int r = arr.length - 1;
  7.     int mid = 0;
  8.     int index = -1;
  9.     while (l <= r) {
  10.         mid = l + ((r - l) >> 2);
  11.         if (arr[mid] <= number) {
  12.             index = mid;
  13.             l = mid + 1;
  14.         } else {
  15.             r = mid - 1;
  16.         }
  17.     }
  18.     return index;
  19. }

给定一个数组arr，已知任何两个相邻的数都不相等，找到随便一个局部最小位置返回

局部最小值问题 定义何为局部最小值： arr[0] < arr[1]，0位置是局部最小； arr[N-1] < arr[N-2]，N-1位置是局部最小； arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小；

  1. public int getLessIndex(int[] arr) {
  2.     if (arr == null) {
  3.         return -1;
  4.     }
  5.     if (arr.length == 1 || arr[0] < arr[1]) {
  6.         return 0;
  7.     }
  8.     if (arr[arr.length - 1] < arr[arr.length - 2]) {
  9.         return arr.length - 1;
  10.     }
  11.     //当以上两个条件都不满足的时候
  12.     //说明整个数组走势是先向下然后再向上的趋势”\……/“(第一个数比第二个数大，最后一个数比倒数第二个数大)，必然存在局部最小
  13.     int l = 1;
  14.     int r = arr.length - 2;
  16.     if (arr[r] < arr[r - 1]) {
  17.         return r;
  18.     }
  19.     int mid = 0;
  20.     while (l < r) {
  21.         mid = l + ((r - l) >> 2);
  22.         if (arr[mid] > arr[mid - 1]) {
  23.             r = mid - 1;
  24.         } else if (arr[mid] > arr[mid + 1]) {
  25.             l = mid + 1;
  26.         } else {
  27.             return mid;
  28.         }
  29.     }
  30.     return l;
  31. }