Java二分查找算法

Dec 27, 2021 阅读(447)

标签: Java 算法

简介 

二分查找又叫折半查找,是一种简单又快速的查找算法;它对要查找的序列有两个要求,一是该序列必须是有序的(即该序列中的所有元素都是按照大小关系排好序的,升序和降序都可以),二是该序列必须是顺序存储的。 

二分查找示例

等值二分查找

@Test
public void testEqBinarySearch() {
    int[] nums = new int[]{1, 4, 6, 6, 6, 19, 21, 22, 23, 30};
    Assert.assertEquals("nums 中有数字 1", true, exists(nums, 1));
    Assert.assertEquals("nums 中有数字 19", true, exists(nums, 19));
    Assert.assertEquals("nums 中有数字 30", true, exists(nums, 30));

    Assert.assertEquals("nums 中没有数字 5", false, exists(nums, 5));
    Assert.assertEquals("nums 中没有数字 7", false, exists(nums, 7));
}


/**
 * 二分等值查找数字是否存在
 * <p>
 * return  存在 true, 不存在 false
 */
private boolean exists(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) {
            return true;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return false;
}

二分查找最接近目标元素的值

@Test
public void testGteBinarySearch() {
    int[] nums = new int[]{1, 4, 6, 6, 6, 19, 21, 22, 23, 30};
    Assert.assertEquals("nums 中下标 >= 0 的元素都 >= 0", 0, firstGteIndex(nums, 0));
    Assert.assertEquals("nums 中下标 >= 0 的元素都 >= 1", 0, firstGteIndex(nums, 1));
    Assert.assertEquals("nums 中下标 >= 2 的元素都 >= 6", 2, firstGteIndex(nums, 6));

    Assert.assertEquals("nums 中下标 >= 5 的元素都 >= 20", 6, firstGteIndex(nums, 20));
    Assert.assertEquals("nums 中下标 >= 5 的元素都 >= 21", 6, firstGteIndex(nums, 21));
    Assert.assertEquals("nums 中最后一个元素 >= 30", nums.length - 1, firstGteIndex(nums, 30));

    Assert.assertEquals("nums 中没有找到 >= 100 的元素", nums.length, firstGteIndex(nums, 100));
}


/**
 * 获取满足 nums[i] >= target , 最小的下标 i, 即找到第一个大于等于 target 元素的下标
 *
 * @param nums
 * @param target
 * @return 如果所有元素都 < target 则返回 nums.length
 */
private int firstGteIndex(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    return l;
}



@Test
public void testGtBinarySearch() {
    int[] nums = new int[]{1, 4, 6, 6, 6, 19, 21, 22, 23, 30};
    Assert.assertEquals("满足 nums[i] > 1 情况, max(i) == 1", 1, firstGtIndex(nums, 1));
    Assert.assertEquals("满足 nums[i] > 6 情况, max(i) == 5", 5, firstGtIndex(nums, 6));

    Assert.assertEquals("满足 nums[i] > 20 情况, max(i) == 6", 6, firstGtIndex(nums, 20));
    Assert.assertEquals("满足 nums[i] > 21 情况, max(i) == 7", 7, firstGtIndex(nums, 21));

    Assert.assertEquals("nums 中没有找到 > 30 的元素", nums.length, firstGtIndex(nums, 30));
    Assert.assertEquals("nums 中没有找到 > 100 的元素", nums.length, firstGtIndex(nums, 100));
}

/**
 * 获取满足 nums[i] > target , 最小的下标 i, 即找到第一个大于 target 元素的下标
 *
 * @param nums
 * @param target
 * @return 如果所有元素都 <= target 则返回 nums.length
 */
private int firstGtIndex(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] <= target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    return l;
}


@Test
public void testLteBinarySearch() {
    int[] nums = new int[]{1, 4, 6, 6, 6, 19, 21, 22, 23, 30};
    Assert.assertEquals("满足 nums[i] <= 1 情况, max(i) == 1", 0, lastLteIndex(nums, 1));
    Assert.assertEquals("满足 nums[i] <= 6 情况, max(i) == 4", 4, lastLteIndex(nums, 6));

    Assert.assertEquals("满足 nums[i] <= 20 情况, max(i) == 5", 5, lastLteIndex(nums, 20));
    Assert.assertEquals("满足 nums[i] <= 21 情况, max(i) == 6", 6, lastLteIndex(nums, 21));

    Assert.assertEquals("满足 nums[i] <= 30 情况, max(i) == nums.length - 1", nums.length - 1, lastLteIndex(nums, 30));
    Assert.assertEquals("nums 中没有找到 <= 0 的元素", -1, lastLteIndex(nums, 0));
}

/**
 * 获取满足 nums[i] <= target , 最大的下标 i
 *
 * @param nums
 * @param target
 * @return 如果所有元素都大于 target 则返回  -1
 */
private int lastLteIndex(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] <= target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    return l - 1;
}


@Test
public void testLtBinarySearch() {
    int[] nums = new int[]{1, 4, 6, 6, 6, 19, 21, 22, 23, 30};
    Assert.assertEquals("nums 中没有找到 < 1 的元素", -1, lastLtIndex(nums, 1));
    Assert.assertEquals("满足 nums[i] < 6 情况, max(i) == 1", 1, lastLtIndex(nums, 6));

    Assert.assertEquals("满足 nums[i] < 20 情况, max(i) == 5", 5, lastLtIndex(nums, 20));
    Assert.assertEquals("满足 nums[i] < 21 情况, max(i) == 5", 5, lastLtIndex(nums, 21));

    Assert.assertEquals("满足 nums[i] < 30 情况, max(i) == nums.length - 2", nums.length - 2, lastLtIndex(nums, 30));
    Assert.assertEquals("满足 nums[i] < 30 情况, max(i) == nums.length - 1", nums.length - 1, lastLtIndex(nums, 31));

    Assert.assertEquals("nums 中没有找到 < 0 的元素", -1, lastLtIndex(nums, 0));
}


/**
 * 获取满足 nums[i] < target , 最大的下标 i
 *
 * @param nums
 * @param target
 * @return 如果所有元素都大于 target 则返回  -1
 */
private int lastLtIndex(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    return l - 1;
}

OJ 是容易出错的地方

int mid = l + (r - l) / 2;     // 正确
int mid = (r + l) / 2;         // 错误,会出现 (r + l) 溢出
int mid = l + (r - l) >> 1;    // 错误, 这个错误写法等价于   (l + (r - l)) >> 1


MongoDB学习园