二分法
二分查找法（Binary Search）是一种高效的搜索算法，其核心思想是将搜索范围每次缩小一半，从而显著降低时间复杂度。
基本原理
要求数据结构已排序（如升序数组）。
- 确定搜索区间：初始时覆盖整个数组。
- 计算中间点：取区间中间位置的元素。
- 比较中间元素：
- 若中间元素等于目标值，返回位置。
- 若中间元素大于目标值，说明目标在左半区间，更新右边界。
- 若中间元素小于目标值，说明目标在右半区间，更新左边界。
- 重复步骤 2-3，直到找到目标值或区间为空。
复杂度
时间复杂度：O(logn)
代码模板 查找目标值
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止整数溢出
if (nums[mid] == target) {
return mid; // 找到目标值
} else if (nums[mid] > target) {
right = mid - 1; // 目标在左半区间
} else {
left = mid + 1; // 目标在右半区间
}
}
return -1; // 未找到目标值
}
查找元素第一次出现的位置
public int searchleft(int[] nums, int target){
int l=0,r=nums.length-1;
int res=-1;
while(l<=r){
int mid = l+(r-l)/2;
if(nums[mid]>=target){
r=mid-1;
}else{
l=mid+1;
}
if(nums[mid]==target) res=mid;
}
return res;
}
查找元素最后一次出现的位置
public int searchright(int[] nums,int target){
int l=0,r=nums.length-1;
int res=-1;
while(l<=r){
int mid = l+(r-l)/2;
if(nums[mid]<=target){
l=mid+1;
}else{
r=mid-1;
}
if(nums[mid]==target) res=mid;
}
return res;
}
例题：