二分查找
- 什么是二分查找?
- 二分查找 demo
- 左右边界查找
-
- 调试
- 总结
什么是二分查找?
对一个有序(局部有序也可)的序列,每次搜索都通过条件判断 target 可能在的搜索区间,排除另一半不可能存在 target 的搜索区间。时间复杂度往往是 O(logn)
二分查找 demo
该模板适用于:查找可以通过访问数组中的单个索引来确定的元素或条件
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
public int search(int[] nums, int target) {
if(nums.length == 0){
return -1;
}
int left,mid,right;
left = 0;
right = nums.length - 1; // 不要忘了右索引的下标是数组长度 -1 ;
while(left<=right){
// 无符号右移 等价于 left + (right-left) / 2 编译器一般会自动转为位运算
mid = (left+right) >>> 1;
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
缺点是遇到重复的target,不能找到最左或最右的那个。
下面是关于左右边界查找的demo。
左右边界查找
使用一个ans 变量保存最新的 mid 边界下标用来返回,不断向左或右减少搜索区间。
// low =true 左搜索,false 右搜索
public int binarysearch(int[] nums,int target,boolean low){
int left,right,mid,ans;
ans = -1;
left = 0;
right = nums.length - 1;
while(left <= right){ // 当 left > right 结束,即 left = right + 1
mid = left + (right-left) / 2;
if(nums[mid] == target){
if(low){
right = mid - 1;
}else{
left = mid + 1;
}
ans = mid;
}else if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}
}
return ans;
}
调试
public class Main {
public static void main(String[] args) {
int[] nums = new int[]{1, 2, 3, 4};
Binarysearch binarysearch = new Binarysearch();
int index = binarysearch.binarysearch(nums, 2);
System.out.println("2 在 {1, 2, 3, 4} 的索引是:" + index);
int[] nums2 = new int[]{1, 2, 2, 2, 4};
int[] nums3 = new int[]{2,2};
int res = binarysearch.binarysearch(nums2, 2, true);
System.out.println("2 在 {1, 2, 2, 2, 4} 的左边界索引是:" + res);
res = binarysearch.binarysearch(nums2, 2, false);
System.out.println("2 在 {1, 2, 2, 2, 4} 的右边界索引是:" + res);
res = binarysearch.binarysearch(nums3, 2, true);
System.out.println("2 在 {2,2} 的左边界索引是:" + res);
res = binarysearch.binarysearch(nums3, 2, false);
System.out.println("2 在 {2,2} 的右边界索引是:" + res);
}
}
2 在 {1, 2, 3, 4} 的索引是:1
2 在 {1, 2, 2, 2, 4} 的左边界索引是:1
2 在 {1, 2, 2, 2, 4} 的右边界索引是:3
2 在 {2,2} 的左边界索引是:0
2 在 {2,2} 的右边界索引是:1
Process finished with exit code 0
总结
二分查找的整体思路关键在于每次搜索要减少一半区间的条件,遇到判断有序数组是否存在某元素时还比较简单,遇到需要查找左右边界的就比较麻烦,需要考虑许多细节,避免死循环,考虑返回值。。。