【程序员必会十大算法】之二分查找算法

1.递归实现

①不考虑相同数

/**
 * 二分查找，不考虑有相同数的情况（递归）
 * @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;
        }
    }
}

②考虑有相同数

/**
 * 二分查找 考虑有相同元素的情况（递归）
 * @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.非递归实现

①不考虑有相同数

/**
 * 二分查找，不考虑有相同数的情况（非递归）
 * @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 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};
        
    }

    /**
     * 二分查找，考虑有相同数的情况（非递归）
     * @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<>();
    }
    /**
     * 二分查找，不考虑有相同数的情况（非递归）
     * @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;
            }
        }
    }

    /**
     * 二分查找，不考虑有相同数的情况（递归）
     * @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;
            }
        }
    }
}