面试常考之手写二分查找

1. 循环实现

    /**
     * 循环实现二分查找
     *
     * @param src
     * @param target
     * @return
     */
    public static int binarySearch(int[] src, int target) {
        int left = 0, right = src.length - 1;
        while (left <= right) {
            int center = left + (right - left >>> 1);
            int centerValue = src[center];
            if (target > centerValue) {
                // 目标值比中间值大  说明在数组右侧  从 center + 1 查找 right
                left = center + 1;
            } else if (target < centerValue) {
                // 目标值比中间值小  说明在数组左侧  从 left 查找 center - 1
                right = center - 1;
            } else {
                return center;
            }
        }
        return -1;
    }

2. 递归实现

    /**
     * 递归实现二分查找
     *
     * @param src
     * @param target
     * @return
     */
    public static int binarySearch2(int[] src, int target) {
        return _binarySearch2(src, 0, src.length - 1, target);
    }

    private static int _binarySearch2(int[] src, int left, int right, int target) {
        if (left <= right) {
            int center = left + (right - left >>> 1);
            int centerValue = src[center];
            if (target > centerValue) {
                // 目标值比中间值大  说明在数组右侧  从 center + 1 查找 right
                return _binarySearch2(src, center + 1, right, target);
            } else if (target < centerValue) {
                // 目标值比中间值小  说明在数组左侧  从 left 查找 center - 1
                return _binarySearch2(src, left, center - 1, target);
            } else {
                return center;
            }
        } else {
            return -1;
        }
    }