1.前提

数组有序

2.思路

image.png

3.含有相同值的数组，只查询到一个的代码

例如：数组{ 1, 8, 10, 89,999,1000,1001,1234 }，查询1000的位置

  1. public class BinarySearch {
  2.     public static void main(String[] args) {
  3.         int arr[] = { 1, 8, 10, 89,999,1000,1001,1234 };
  4.         int resIndex = binarySearch(arr, 0, arr.length - 1, 1000);
  5.         System.out.println(resIndex);
  6.     }
  8.     public static int binarySearch(int[] arr, int left, int right, int findVal){
  10.         // 当 left > right 时，说明递归整个数组，但是没有找到
  11.         if (left>right){
  12.             return  -1;
  13.         }
  14.         int mid = (left + right) / 2;
  15.         int midVal = arr[mid];
  16.         if (findVal > midVal){// 向 右递归
  17.             return binarySearch(arr,mid+1,right,findVal);
  18.         }else if (findVal < midVal) { // 向左递归
  19.             return binarySearch(arr, left, mid - 1, findVal);
  20.         } else {
  21.             return mid;
  22.         }
  23.     }

运行结果

  1. 5//元素1000对应的数组下标为5

4.增强版（查询所有满足条件的元素下标）

如：查询数组 { 1, 8, 10, 89,1000,1000,1000,1234 }中 1000的元素下标

  1. public class BinarySearch {
  2.     public static void main(String[] args) {
  3.         int arr[] = { 1, 8, 10, 89,1000,1000,1000,1234 };
  4.         int resIndex = binarySearch(arr, 0, arr.length - 1, 1000);
  5.         List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
  6.         System.out.println("resIndexList=" + resIndexList);
  8.     }
  11.     public static List<Integer>  binarySearch2(int[] arr, int left, int right, int findVal) {
  12.         // 当 left > right 时，说明递归整个数组，但是没有找到
  13.         if (left > right) {
  14.             return new ArrayList<Integer>();
  15.         }
  16.         int mid = (left + right) / 2;
  17.         int midVal = arr[mid];
  19.         if (findVal > midVal) { // 向 右递归
  20.             return binarySearch2(arr, mid + 1, right, findVal);
  21.         } else if (findVal < midVal) { // 向左递归
  22.             return binarySearch2(arr, left, mid - 1, findVal);
  23.         } else {
  24. //             * 思路分析
  25. //             * 1. 在找到mid 索引值，不要马上返回
  26. //             * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  27. //             * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  28. //             * 4. 将Arraylist返回
  29.             List<Integer> resindexlist = new ArrayList<Integer>();
  30.             //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  31.             int temp = mid - 1;
  32.             while (true) {
  33.                 if (temp < 0 || arr[temp] != findVal) {//退出
  34.                     break;
  35.                 }
  36.                 //否则，就temp 放入到 resIndexlist
  37.                 resindexlist.add(temp);
  38.                 temp -= 1;//temp左移
  39.             }
  40.             resindexlist.add(mid);//将第一次找到的值加入列表
  42.             temp = mid + 1;
  43.             while (true) {
  44.                 if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
  45.                     break;
  46.                 }
  47.                 //否则，就temp 放入到 resIndexlist
  48.                 resindexlist.add(temp);
  49.                 temp += 1;//temp左移
  50.             }
  51.             return resindexlist;
  52.         }
  53.     }
  55. }

运行结果

  1. resIndexList=[4, 5, 6]