二分查找（序列是顺序的运用递归）

谁借莪１个温暖的怀抱￠ 2021-11-04 11:04 204阅读 0赞

package com.search;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @Auther: 大哥的叔
     * @Date: 2019/8/9 17:21
     * @Description:
     */
    //注意：使用二分查找的前提是 该数组是有序的
    public class BinarySearch {
        public static void main (String[] args) {
            int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
            int resIndex = binarySearch(arr,0,arr.length-1,89);
            System.out.println(resIndex);
    
            List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
            System.out.println("resIndexList=" + resIndexList);
        }
    
    
         // 二分查找算法
         /**
         *
         * @param arr
         *            数组
         * @param left
         *            左边的索引
         * @param right
         *            右边的索引
         * @param findVal
         *            要查找的值
         * @return 如果找到就返回下标，如果没有找到，就返回 -1
         */
        public static int binarySearch(int[] arr,int left,int right,int findVal){
            if (left > right) {
                return -1;
            }
            int mid = (left+right)/2;
            int midVal = arr[mid];
            if (findVal>midVal){
                return binarySearch(arr,mid+1,right,findVal);
                }else if (findVal<midVal){
                return binarySearch(arr,left,mid -1,findVal);
            }else {
                return mid;
            }
        }
    
        /*
         * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
         * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
         *
         * 思路分析
         * 1. 在找到mid 索引值，不要马上返回
         * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
         * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
         * 4. 将Arraylist返回
         */
        public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
            System.out.println("hello~");
            // 当 left > right 时，说明递归整个数组，但是没有找到
            if (left > right) {
                return new ArrayList<Integer>();
            }
            int mid = (left + right) / 2;
            int midVal = arr[mid];
    
            if (findVal > midVal) { // 向 右递归
                return binarySearch2(arr, mid + 1, right, findVal);
            } else if (findVal < midVal) { // 向左递归
                return binarySearch2(arr, left, mid - 1, findVal);
            } else {
    //			 * 思路分析
    //			 * 1. 在找到mid 索引值，不要马上返回
    //			 * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    //			 * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
    //			 * 4. 将Arraylist返回
    
                List<Integer> resIndexlist = new ArrayList<Integer>();
                //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
                int temp = mid - 1;
                while(true) {
                    if (temp < 0 || arr[temp] != findVal) {//退出
                        break;
                    }
                    //否则，就temp 放入到 resIndexlist
                    resIndexlist.add(temp);
                    temp -= 1; //temp左移
                }
                resIndexlist.add(mid);  //
    
                //向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
                temp = mid + 1;
                while(true) {
                    if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
                        break;
                    }
                    //否则，就temp 放入到 resIndexlist
                    resIndexlist.add(temp);
                    temp += 1; //temp右移
                }
    
                return resIndexlist;
            }
    
        }
    }