简介
二分查找又叫折半查找，是一种简单又快速的查找算法；它对要查找的序列有两个要求，一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以），二是该序列必须是顺序存储的。
二分查找示例
等值二分查找
@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
