二分法查找

一、思路

二、注意

1. 结束条件一定是left >= right 就结束了
2. 当查找的值在数组中存在多个值时，就需要在值对应数组下标的左右两边进行查找，看是否有相同值。并将其保存在集合中
3. 查找到最后永远都是 mid == findVal的。
4. 比较查找的值findVal 是否大于中间下标对应的值时，一定注意比较的是 值 不是findVal与中间下标相比较。findVal > array[mid]

三、代码

/**
 * @Description 二分查找，递归版
 * @Author Meng
 * @Versions
 * @Date 2021-07-20-20:57
 */
public class BinarySearch {
    public static void main(String[] args) {
//        int[] array = { 1, 8, 10, 89,1000,1000, 1234};
        int array[] = { 1, 2, 3, 4, 5, 6, 7};
        List<Integer> resultList = binarySearch(array, 0, array.length, 9);
        System.out.println(resultList);

    }
     /**
     * 
     * @param array 进行查找的有序数组
     * @param left 左边下标
     * @param right 右边下标
     * @param findVal 带查找的值
     * @return 返回数组中查找到的对应值的下标
     */ 
    public static List<Integer> binarySearch(int[] array, int left, int right, int findVal){
        ArrayList<Integer> arrayList = new ArrayList<>();
        // 当左边的下标大于右边下标时结束递归
        if (left >= right){
            return new ArrayList<Integer>();
        }

        int mid = (left + right) / 2;
        if (findVal > array[mid]){
            return binarySearch(array, mid + 1, right, findVal);
        }else if (findVal < array[mid]){
            return binarySearch(array, left, mid, findVal);
        }else{
            /*
     * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
     * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
     * 
     * 思路分析
     * 1. 在找到mid 索引值，不要马上返回
     * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
     * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
     * 4. 将Arraylist返回
     */
            int temp = mid;
            while (true){
                if (temp < left || array[temp] != findVal){
                    break;
                }
                arrayList.add(temp);
                temp -=1;
            }
            temp = mid + 1;
            while (true){
                if (temp > right || array[temp] != findVal){
                    break;
                }
                arrayList.add(temp);
                temp += 1;
            }
        }
        return arrayList;
    }
}