1. package com.atguigu.search;
    3. /**
    4.  * ClassName:  <br/>
    5.  * Description:  <br/>
    6.  * Date: 2021-02-23 15:14 <br/>
    7.  * <br/>
    8.  *
    9.  * @author yufengming
    10.  * @version 产品版本信息 2021年02月23日15:14分 yufengming(yufengming@travelsky.com) 新建<br/>
    11.  * <p>
    12.  * 修改记录
    13.  * @email yufengming@travelsky.com
    14.  * @project data_algorithm
    15.  * @package com.atguigu.search
    16.  */
    18. import java.util.ArrayList;
    19. import java.util.List;
    21. //注意：使用二分查找的前提是 该数组是有序的.
    22. public class BinarySearch {
    24.     public static void main(String[] args) {
    25.         //int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
    26.         int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
    29.         //
    30. //        int resIndex = binarySearch(arr, 0, arr.length - 1, 1000);
    31. //        System.out.println("resIndex=" + resIndex);
    33.         List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1);
    34.         System.out.println("resIndexList=" + resIndexList);
    35.     }
    37.     /**
    38.      * 二分查找算法
    39.      * @param arr 数组
    40.      * @param left 左边的索引
    41.      * @param right 右边的索引
    42.      * @param findVal 要查找的值
    43.      * @return 如果找到就返回下标，如果没有找到，就返回 -1
    44.      */
    45.     public static int binarySearch(int[] arr, int left, int right, int findVal) {
    48.         // 当 left > right 时，说明递归整个数组，但是没有找到
    49.         if (left > right) {
    50.             return -1;
    51.         }
    52.         int mid = (left + right) / 2;
    53.         int midVal = arr[mid];
    55.         if (findVal > midVal) { // 向 右递归
    56.             return binarySearch(arr, mid + 1, right, findVal);
    57.         } else if (findVal < midVal) { // 向左递归
    58.             return binarySearch(arr, left, mid - 1, findVal);
    59.         } else {
    61.             return mid;
    62.         }
    64.     }
    66.     //完成一个课后思考题:
    67.     /*
    68.      * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
    69.      * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
    70.      *
    71.      * 思路分析
    72.      * 1. 在找到mid 索引值，不要马上返回
    73.      * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    74.      * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    75.      * 4. 将Arraylist返回
    76.      */
    78.     public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
    80.         System.out.println("hello~");
    81.         // 当 left > right 时，说明递归整个数组，但是没有找到
    82.         if (left > right) {
    83.             return new ArrayList<Integer>();
    84.         }
    85.         int mid = (left + right) / 2;
    86.         int midVal = arr[mid];
    88.         if (findVal > midVal) { // 向 右递归
    89.             return binarySearch2(arr, mid + 1, right, findVal);
    90.         } else if (findVal < midVal) { // 向左递归
    91.             return binarySearch2(arr, left, mid - 1, findVal);
    92.         } else {
    93. //             * 思路分析
    94. //             * 1. 在找到mid 索引值，不要马上返回
    95. //             * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    96. //             * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    97. //             * 4. 将Arraylist返回
    99.             List<Integer> resIndexlist = new ArrayList<Integer>();
    100.             //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    101.             int temp = mid - 1;
    102.             while(true) {
    103.                 if (temp < 0 || arr[temp] != findVal) {//退出
    104.                     break;
    105.                 }
    106.                 //否则，就temp 放入到 resIndexlist
    107.                 resIndexlist.add(temp);
    108.                 temp -= 1; //temp左移
    109.             }
    110.             resIndexlist.add(mid);  //
    112.             //向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    113.             temp = mid + 1;
    114.             while(true) {
    115.                 if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
    116.                     break;
    117.                 }
    118.                 //否则，就temp 放入到 resIndexlist
    119.                 resIndexlist.add(temp);
    120.                 temp += 1; //temp右移
    121.             }
    123.             return resIndexlist;
    124.         }
    126.     }
    127. }
    1. hello~
    2. hello~
    3. hello~
    4. hello~
    5. resIndexList=[0]
    7. Process finished with exit code 0