zcq

    1. package com.atguigu.search;
    3. import java.util.ArrayList;
    4. import java.util.List;
    6. //注意：使用二分查找的前提是 该数组是有序的.
    7. public class BinarySearch {
    9.     public static void main(String[] args) {
    10.         //int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
    11.         int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
    14.         //
    15. //        int resIndex = binarySearch(arr, 0, arr.length - 1, 1000);
    16. //        System.out.println("resIndex=" + resIndex);
    18.         List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1);
    19.         System.out.println("resIndexList=" + resIndexList);
    20.     }
    22.     // 二分查找算法
    23.     /**
    24.      * 
    25.      * @param arr
    26.      *            数组
    27.      * @param left
    28.      *            左边的索引
    29.      * @param right
    30.      *            右边的索引
    31.      * @param findVal
    32.      *            要查找的值
    33.      * @return 如果找到就返回下标，如果没有找到，就返回 -1
    34.      */
    35.     public static int binarySearch(int[] arr, int left, int right, int findVal) {
    38.         // 当 left > right 时，说明递归整个数组，但是没有找到
    39.         if (left > right) {
    40.             return -1;
    41.         }
    42.         int mid = (left + right) / 2;
    43.         int midVal = arr[mid];
    45.         if (findVal > midVal) { // 向 右递归
    46.             return binarySearch(arr, mid + 1, right, findVal);
    47.         } else if (findVal < midVal) { // 向左递归
    48.             return binarySearch(arr, left, mid - 1, findVal);
    49.         } else {
    51.             return mid;
    52.         }
    54.     }
    56.     //完成一个课后思考题:
    57.     /*
    58.      * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
    59.      * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
    60.      * 
    61.      * 思路分析
    62.      * 1. 在找到mid 索引值，不要马上返回
    63.      * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    64.      * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    65.      * 4. 将Arraylist返回
    66.      */
    68.     public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
    70.         System.out.println("hello~");
    71.         // 当 left > right 时，说明递归整个数组，但是没有找到
    72.         if (left > right) {
    73.             return new ArrayList<Integer>();
    74.         }
    75.         int mid = (left + right) / 2;
    76.         int midVal = arr[mid];
    78.         if (findVal > midVal) { // 向 右递归
    79.             return binarySearch2(arr, mid + 1, right, findVal);
    80.         } else if (findVal < midVal) { // 向左递归
    81.             return binarySearch2(arr, left, mid - 1, findVal);
    82.         } else {
    83. //             * 思路分析
    84. //             * 1. 在找到mid 索引值，不要马上返回
    85. //             * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    86. //             * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    87. //             * 4. 将Arraylist返回
    89.             List<Integer> resIndexlist = new ArrayList<Integer>();
    90.             //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    91.             int temp = mid - 1;
    92.             while(true) {
    93.                 if (temp < 0 || arr[temp] != findVal) {//退出
    94.                     break;
    95.                 }
    96.                 //否则，就temp 放入到 resIndexlist
    97.                 resIndexlist.add(temp);
    98.                 temp -= 1; //temp左移
    99.             }
    100.             resIndexlist.add(mid);  //
    102.             //向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    103.             temp = mid + 1;
    104.             while(true) {
    105.                 if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
    106.                     break;
    107.                 }
    108.                 //否则，就temp 放入到 resIndexlist
    109.                 resIndexlist.add(temp);
    110.                 temp += 1; //temp右移
    111.             }
    113.             return resIndexlist;
    114.         }
    116.     }
    117. }