二分法查找排序数组中的元素

二分法查找排序数组中的元素使用汇总。

示例排序数组：

private int[] nums = {2,4,6,8,10,12,14,16,18};

查找指定值

public int equalVal(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            return nums[mid];
        } else if (nums[mid] > target) {//查找左边的
            high = mid - 1;
        } else {//查找右边的
            low = mid + 1;
        }
    }
    return -1;
}

测试用例：

assertEquals(solution.equalVal(nums, 3), -1);
assertEquals(solution.equalVal(nums, 6), 6);
assertEquals(solution.equalVal(nums, 16), 16);
assertEquals(solution.equalVal(nums, 22), -1);
assertEquals(solution.equalVal(nums, 2), 2);

查找小于目标值的最大值

public int maxVal2low(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        // 这样的操作是为了取高位
        int mid = (low + high + 1) / 2;
        if (nums[mid] < target) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    if (nums[low] < target) {
        return nums[low];
    } else {
        return -1;
    }
}

测试用例：

assertEquals(solution.maxVal2low(nums, 3), 2);
assertEquals(solution.maxVal2low(nums, 6), 4);
assertEquals(solution.maxVal2low(nums, 16), 14);
assertEquals(solution.maxVal2low(nums, 22), 18);
assertEquals(solution.maxVal2low(nums, 1), -1);
assertEquals(solution.maxVal2low(nums, 2), -1);

查找小于等于目标值的最大值

public int maxVal2lowOrEqual(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        // 这样的操作是为了取高位
        int mid = (low + high + 1) / 2;
        if (nums[mid] <= target) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    if (nums[low] <= target) {
        return nums[low];
    } else {
        return -1;
    }
}

测试用例：

assertEquals(solution.maxVal2lowOrEqual(nums, 3), 2);
assertEquals(solution.maxVal2lowOrEqual(nums, 6), 6);
assertEquals(solution.maxVal2lowOrEqual(nums, 1), -1);
assertEquals(solution.maxVal2lowOrEqual(nums, 2), 2);

查找大于目标值的最小值

public int minVal2high(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        if (nums[mid] <= target) {
            low = mid + 1;
        } else { //a[mid] > key
            high = mid;   //因为mid也满足情况
        }
    }
    if (nums[high] > target) {
        return nums[high];
    } else {
        return -1;
    }
}

测试用例：

assertEquals(solution.minVal2high(nums, 3), 4);
assertEquals(solution.minVal2high(nums, 6), 8);
assertEquals(solution.minVal2high(nums, 16), 18);
assertEquals(solution.minVal2high(nums, 18), -1);
assertEquals(solution.minVal2high(nums, 22), -1);

查找大于等于目标值的最小值

public int minVal2highOrEqual(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        if (nums[mid] < target) {
            low = mid + 1;
        } else { //a[mid] >= key
            high = mid;   //因为mid也满足情况
        }
    }
    if (nums[high] >= target) {
        return nums[high];
    } else {
        return -1;
    }
}

测试用例：

assertEquals(solution.minVal2highOrEqual(nums, 3), 4);
assertEquals(solution.minVal2highOrEqual(nums, 6), 6);
assertEquals(solution.minVal2highOrEqual(nums, 16), 16);
assertEquals(solution.minVal2highOrEqual(nums, 18), 18);
assertEquals(solution.minVal2highOrEqual(nums, 22), -1);