1.遞歸實(shí)現(xiàn)

①不考慮相同數(shù)

/** * 二分查找，不考慮有相同數(shù)的情況（遞歸） * @param arr * @param left * @param right * @param findVal * @return */public static int binarySearch(int[] arr,int left,int right,int findVal){    if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){        return -1;    }else {        int mid = (left + right) / 2;        if (arr[mid] > findVal){            return binarySearch(arr,left,mid - 1,findVal);        }else if (arr[mid] < findVal){            return binarySearch(arr,mid + 1,right,findVal);        }else {            //找到了            return mid;        }    }}

②考慮有相同數(shù)

/** * 二分查找 考慮有相同元素的情況（遞歸） * @param arr * @param left * @param right * @param findVal 要查找的值 * @return */public static ArrayList<Integer> binarySearch1(int[] arr,int left,int right,int findVal){    if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){        return null;    }else {        int mid = (left + right) / 2;        if (arr[mid] > findVal){            return binarySearch1(arr,left,mid - 1,findVal);        }else if (arr[mid] < findVal){            return binarySearch1(arr,mid + 1,right,findVal);        }else {            ArrayList<Integer> arrayList = new ArrayList<>();            //先往左走            int midLeft = mid - 1;            while (midLeft >= 0 && arr[midLeft] == findVal){                arrayList.add(midLeft);                midLeft--;            }            Collections.reverse(arrayList);            arrayList.add(mid);            int midRight = mid + 1;            while (midRight < arr.length && arr[midRight] == findVal){                arrayList.add(midRight);                midRight++;            }            return arrayList;        }    }}

2.非遞歸實(shí)現(xiàn)

①不考慮有相同數(shù)

/** * 二分查找，不考慮有相同數(shù)的情況（非遞歸） * @param arr * @param findVal * @return */public static int binarySearch3(int[] arr,int findVal){    int left = 0;    int right = arr.length - 1;    while (left <= right){        int mid = (left + right) / 2;        if (arr[mid] > findVal){            right = mid - 1;        }else if (arr[mid] < findVal){            left = mid + 1;        }else {            return mid;        }    }    return -1;}

②考慮有相同數(shù)

/** * 二分查找，考慮有相同數(shù)的情況（非遞歸） * @param arr * @param findVal * @return */public static ArrayList<Integer> binarySearch4(int[] arr,int findVal){    int left = 0;    int right = arr.length - 1;    while (left <= right){        int mid = (left + right) / 2;        if (arr[mid] > findVal){            right = mid - 1;        }else if (arr[mid] < findVal){            left = mid + 1;        }else {            ArrayList<Integer> arrayList = new ArrayList<>();            int midLeft = mid - 1;            while (midLeft > 0 && arr[midLeft] == findVal){                arrayList.add(midLeft);                midLeft--;            }            Collections.reverse(arrayList);            arrayList.add(mid);            int midRight = mid + 1;            while (midRight < arr.length && arr[midRight] == findVal){                arrayList.add(midRight);                midRight++;            }            return arrayList;        }    }    return new ArrayList<>();}

完整版

public class Main {    public static void main(String[] args) {        int[] arr = {1,1,2,2,33};            }    /**     * 二分查找，考慮有相同數(shù)的情況（非遞歸）     * @param arr     * @param findVal     * @return     */    public static ArrayList<Integer> binarySearch4(int[] arr,int findVal){        int left = 0;        int right = arr.length - 1;        while (left <= right){            int mid = (left + right) / 2;            if (arr[mid] > findVal){                right = mid - 1;            }else if (arr[mid] < findVal){                left = mid + 1;            }else {                ArrayList<Integer> arrayList = new ArrayList<>();                int midLeft = mid - 1;                while (midLeft > 0 && arr[midLeft] == findVal){                    arrayList.add(midLeft);                    midLeft--;                }                Collections.reverse(arrayList);                arrayList.add(mid);                int midRight = mid + 1;                while (midRight < arr.length && arr[midRight] == findVal){                    arrayList.add(midRight);                    midRight++;                }                return arrayList;            }        }        return new ArrayList<>();    }    /**     * 二分查找，不考慮有相同數(shù)的情況（非遞歸）     * @param arr     * @param findVal     * @return     */    public static int binarySearch3(int[] arr,int findVal){        int left = 0;        int right = arr.length - 1;        while (left <= right){            int mid = (left + right) / 2;            if (arr[mid] > findVal){                right = mid - 1;            }else if (arr[mid] < findVal){                left = mid + 1;            }else {                return mid;            }        }        return -1;    }    /**     * 二分查找 考慮有相同元素的情況（遞歸）     * @param arr     * @param left     * @param right     * @param findVal 要查找的值     * @return     */    public static ArrayList<Integer> binarySearch1(int[] arr,int left,int right,int findVal){        if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){            return null;        }else {            int mid = (left + right) / 2;            if (arr[mid] > findVal){                return binarySearch1(arr,left,mid - 1,findVal);            }else if (arr[mid] < findVal){                return binarySearch1(arr,mid + 1,right,findVal);            }else {                ArrayList<Integer> arrayList = new ArrayList<>();                //先往左走                int midLeft = mid - 1;                while (midLeft >= 0 && arr[midLeft] == findVal){                    arrayList.add(midLeft);                    midLeft--;                }                Collections.reverse(arrayList);                arrayList.add(mid);                int midRight = mid + 1;                while (midRight < arr.length && arr[midRight] == findVal){                    arrayList.add(midRight);                    midRight++;                }                return arrayList;            }        }    }    /**     * 二分查找，不考慮有相同數(shù)的情況（遞歸）     * @param arr     * @param left     * @param right     * @param findVal     * @return     */    public static int binarySearch(int[] arr,int left,int right,int findVal){        if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){            return -1;        }else {            int mid = (left + right) / 2;            if (arr[mid] > findVal){                return binarySearch(arr,left,mid - 1,findVal);            }else if (arr[mid] < findVal){                return binarySearch(arr,mid + 1,right,findVal);            }else {                //找到了                return mid;            }        }    }}