前提

必须是有序数组。

思路

image.png

无重复数组二分查找

package com.pl.arithmetic.search;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName BinarySearch
 * @Author pl
 * @Date 2020/12/20
 * @Version V1.0.0
 */
public class BinarySearch {

    public static void main(String[] args) {
       int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
        int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
        System.out.println("resIndex=" + resIndex);
    }


    public static int binarySearch(int[] arr,int leftIndex,int rightIndex,int targetValue){
        //todo 先判断是否需要查找
        if (leftIndex>rightIndex){
            return -1;
        }
        //todo 中指比较,递归查找
        int midIndex =  (leftIndex+rightIndex)/2;
        int midValue = arr[midIndex];
        if (midValue == targetValue){
            return midIndex;
        }
        //和midValue比较，如果小于midValue，左递归，反之右递归
        if (midValue>targetValue){
            return binarySearch(arr,0, midIndex-1,targetValue);
        }else {
            return binarySearch(arr,midIndex+1,rightIndex,targetValue);
        }
    }
}

有重复数组二分查找

思路

1.退出条件
leftIndx>rightIndex
2.中值比较
如果相等，先不退出，因为前提是有序数组，找其左右是否也有相同值，直到左右都不等于targetValue
3.二分递归

package com.pl.arithmetic.search;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName BinarySearch
 * @Author pl
 * @Date 2020/12/20
 * @Version V1.0.0
 */
public class BinarySearch {

    public static void main(String[] args) {
        int arr[] = { 1, 8, 10, 89,1000,1000,1000, 1234 };
       // int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
        //
    /*  int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
        System.out.println("resIndex=" + resIndex);*/

        List<Integer> resIndexList = binarySearchPlus(arr, 0, arr.length - 1, 1000);
        System.out.println("resIndexList=" + resIndexList);
    }


    public static int binarySearch(int[] arr,int leftIndex,int rightIndex,int targetValue){
        //todo 先判断是否需要查找
        if (leftIndex>rightIndex){
            return -1;
        }
        //todo 中指比较,递归查找
        int midIndex =  (leftIndex+rightIndex)/2;
        int midValue = arr[midIndex];
        if (midValue == targetValue){
            return midIndex;
        }
        //和midValue比较，如果小于midValue，左递归，反之右递归
        if (midValue>targetValue){
            return binarySearch(arr,0, midIndex-1,targetValue);
        }else {
            return binarySearch(arr,midIndex+1,rightIndex,targetValue);
        }
    }

    //完成一个课后思考题:
    /*
     * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
     * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
     *
     * 思路分析
     * 1. 在找到mid 索引值，不要马上返回
     * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
     * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
     * 4. 将Arraylist返回
     */
    public static List<Integer> binarySearchPlus(int[] arr, int leftIndex, int rightIndex, int targetValue){
        //todo 先判断是否需要查找
        //只有遍历了整个数组都没找到所要的targetValue才会到满足这个条件
        if (leftIndex>rightIndex){
            return new ArrayList<Integer>();
        }
        //todo 递归查找，中指比较,找到后不立即退出，因为二分查找前提是有序数组，需要查找其值左右是否为要找的项，左右两边查找，直到其左右两边都不等于targetValue，返回targetIndexList
        int midIndex =  (leftIndex+rightIndex)/2;
        int midValue = arr[midIndex];
        if (midValue == targetValue){
            List<Integer> targetIndexList = new ArrayList<>();
            targetIndexList.add(midIndex);
            //从midIndex左面线性查找
            int midLeftIndex = midIndex -1;
            while (true){
                if (midLeftIndex<leftIndex || arr[midLeftIndex]!=targetValue){
                    break;
                }
                targetIndexList.add(midLeftIndex);
                midLeftIndex--;
            }
            //从midIndex右面查找
            int midRightIndex = midIndex+1;
            while (true){
                if (midRightIndex>rightIndex || arr[midRightIndex] != targetValue){
                    break;
                }
                targetIndexList.add(midRightIndex);
                midRightIndex++;
            }
            return targetIndexList;
        }
        //和midValue比较，如果小于midValue，左递归，反之右递归
        if (midValue>targetValue){
            return binarySearchPlus(arr,0, midIndex-1,targetValue);
        }else {
            return binarySearchPlus(arr,midIndex+1,rightIndex,targetValue);
        }
    }
}

错误code

package com.pl.arithmetic.search;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName BinarySearch
 * @Author pl
 * @Date 2020/12/20
 * @Version V1.0.0
 */
public class BinarySearch {

    public static void main(String[] args) {
        int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
       // int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
        //
    /*  int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
        System.out.println("resIndex=" + resIndex);*/

        List<Integer> resIndexList = binarySearchPlus(arr, 0, arr.length - 1, 1000);
        System.out.println("resIndexList=" + resIndexList);
    }


    public static int binarySearch(int[] arr,int leftIndex,int rightIndex,int targetValue){
        //todo 先判断是否需要查找
        if (leftIndex>rightIndex){
            return -1;
        }
        //todo 中指比较,递归查找
        int midIndex =  (leftIndex+rightIndex)/2;
        int midValue = arr[midIndex];
        if (midValue == targetValue){
            return midIndex;
        }
        //和midValue比较，如果小于midValue，左递归，反之右递归
        if (midValue>targetValue){
            return binarySearch(arr,0, midIndex-1,targetValue);
        }else {
            return binarySearch(arr,midIndex+1,rightIndex,targetValue);
        }
    }

    //完成一个课后思考题:
    /*
     * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
     * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
     *
     * 思路分析
     * 1. 在找到mid 索引值，不要马上返回
     * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
     * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
     * 4. 将Arraylist返回
     */
    public static List<Integer> binarySearchPlus(int[] arr, int leftIndex, int rightIndex, int targetValue){
        //todo 先判断是否需要查找
        //只有遍历了整个数组都没找到所要的targetValue才会到满足这个条件
        if (leftIndex>rightIndex){
            return new ArrayList<Integer>();
        }
        //todo 递归查找，中指比较,找到后不立即退出，因为二分查找前提是有序数组，需要查找其值左右是否为要找的项，左右两边查找，直到其左右两边都不等于targetValue，返回targetIndexList
        int midIndex =  (leftIndex+rightIndex)/2;
        int midValue = arr[midIndex];
        if (midValue == targetValue){
            List<Integer> targetIndexList = new ArrayList<>();
            targetIndexList.add(midIndex);
            //从midIndex左面线性查找
            int midLeftIndex = --midIndex;
            while (true){
                if (midLeftIndex<leftIndex || arr[midLeftIndex]!=targetValue){
                    break;
                }
                targetIndexList.add(midLeftIndex);
                midLeftIndex--;
            }
            //从midIndex右面查找
            int midRightIndex = ++midIndex;
            while (true){
                if (midRightIndex>rightIndex || arr[midRightIndex] != targetValue){
                    break;
                }
                targetIndexList.add(midRightIndex);
                midRightIndex++;
            }
            return targetIndexList;
        }
        //和midValue比较，如果小于midValue，左递归，反之右递归
        if (midValue>targetValue){
            return binarySearchPlus(arr,0, midIndex-1,targetValue);
        }else {
            return binarySearchPlus(arr,midIndex+1,rightIndex,targetValue);
        }
    }
}

输出[5,4,5]

analyze

73,82行出错
int midLeftIndex = --midIndex;
int midRightIndex = ++midIndex;
这样赋值，midIndex内存地质发生变化