Java 版二分查找算法

• 概述
• 二分查找
• 总结

  这里我用 Java 语言实现了二分查找算法，虽然该算法的思维非常容易理解，但是在细节之处，比如在查找的边界上有很多值得注意的地方，这里不容小视。

  如下是代码所示，请大家注意边界的处理，具体解释的话可以参考这个链接 – 二分查找的几种写法。

public class Test {
    
    public static void main(String[] args) {
        // find 5 in arr[4], arr[5], arr[6]
        int[] arr = {1, 2, 3, 4, 5, 5, 5, 6, 7, 8};

        System.out.println(binSearch(arr, arr.length, 5));
        System.out.println(binSearchFindStart(arr, arr.length, 5));
        System.out.println(binSearchFindEnd(arr, arr.length, 5));
        System.out.println(binSearchAnotherWay(arr, arr.length, 5));
    }

    // 二分查找，左闭右开
    public static int binSearch(int[] arr, int size, int target) {
        int start = 0, end = size;

        while (start < end) {
            int mid = start + (end - start) / 2;  // 防止整数相加溢出

            if (arr[mid] == target)
                return mid;
            else if (arr[mid] < target)
                start = mid + 1;
            else if (arr[mid] > target)
                end = mid;
        }

        return -1;
    }

    // 二分查找，寻找最开始等于目标值的位置
    public static int binSearchFindStart(int[] arr, int size, int target) {
        int start = 0, end = size;
        int flag = -1;

        while (start < end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                flag = 1;  // 表明存在目标值
                end = mid;
            }
            else if (arr[mid] < target)
                start = mid + 1;
            else if (arr[mid] > target)
                end = mid;
        }

        return flag == 1 ? start : flag;
    }

    // 二分查找，寻找最后等于目标值的位置
    public static int binSearchFindEnd(int[] arr, int size, int target) {
        int start = 0, end = size;
        int flag = -1;

        while (start < end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                flag = 1;  // 表明存在目标值
                start = mid + 1;
            }
            else if (arr[mid] < target)
                start = mid + 1;
            else if (arr[mid] > target)
                end = mid;
        }

        return flag == 1 ? end - 1 : flag;
    }

	// 二分查找，闭区间的写法
    public static int binSearchAnotherWay(int[] arr, int size, int target) {
        int start = 0, end = size - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) 
                return mid;
            else if (arr[mid] < target) 
                start = mid + 1;
            else if (arr[mid] > target) 
                end = mid - 1;
        }

        return -1;
    }
}

不忘初心，砥砺前行！