[Java 算法] 二分查找

练习一 : 二分查找

704. 二分查找 – 力扣（LeetCode）

class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1,mid = 0;
while(left<=right){
mid = left+(right-left)/2;//防止溢出
if(nums[mid] == target){
return mid;
}else if(nums[mid]>target){
right = mid-1;
}else{//nums[mid]<target
left = mid+1;
}
}
return -1;
}
}

算法原理 :

⭐⭐⭐练习二 : 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 – 力扣（LeetCode）

class Solution {
public int[] searchRange(int[] nums, int target) {
int len = nums.length;
int left = 0,right = len-1,mid = 0;
int[] ret = {-1,-1};
if(len == 0||nums[len-1]<target||nums[0]>target){//把数组为空必免指针越界的优先级排到最高
return ret;
}
//找左端点
int retleft = 0;
while(left<right){
mid = left+(right-left)/2;
//找左端点时,如果存在则最后mid会落在left处,经过处理会让两个指针重合,退出循环,返回结果
if(nums[mid]<target){
left = mid+1;
}else{
right = mid;
}
}
//判断双指针重合处是否是端点
if(nums[left] != target){
return ret;
}
retleft = left;

//找右端点
int retright = 0;
left = 0;
right = len-1;//记得恢复指针
while(left<right){
mid = left+(right-left+1)/2;
//找右端点时,如果存在则最后mid会落在right处,经过处理会让left和right重合,退出循环,返回结果
if(nums[mid]<=target){
left = mid;
}else {
right = mid-1;
}
}
retright = right;
//经过找左端点后如果进入到寻找右端点,则数组中一定包含target,此时不需要进行判断
ret[0] = retleft;
ret[1] = retright;
return ret;
}
}

算法原理 :

找左端点 :

• 当 mid 落在<target 处 , 要让 left 跳出非法区域(left = mid+1)
• 当 mid 落在>=target 处 , 要让 right 移到 mid 处(right = mid),因为不能保证 mid-1 和 mid 处是否是左端点
• 当退出本次循环时 , 还需要判断一下双指针重合位置是否是 target

找右端点 :

• 和找左端点同理;当 mid 落在<=target 处 , 要让 left 移到 mid 处(left = mid),因为不能保证 mid+1 和 mid 处是右端点
• 当 mid 落在>target 处 , 要让 right 跳出非法区域(right = mid-1)
• 能进入此次循环,意味着数组中一定包含 target , 所以不需要判断双指针位置的合法性(即使数组中只有一个 target)

注意 :

因为当只有当两指针重合时(right == left) , 才能退出循环 , 判断合法性 ; 如果写成 left<=right , 则最后一步 right == left ==mid 时会一直死循环

找左端点 → 用「左中位数」：mid = left + (right – left)/2

找右端点 → 用「右中位数」：mid = left + (right – left + 1)/2

左中数 : 处理后 mid 会更靠近 left , 直到 等于 left ; 目的是让 right 主动向左收敛 , 最终重合

右中数 : 处理后 mid 会更靠近 right , 直到 等于 righr ; 目的是让 left 主动向右收敛 , 最终重合

核心模板 :

练习三 : 搜索插入位置

35. 搜索插入位置 – 力扣（LeetCode）

class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0,right = nums.length-1,mid = 0;
while(left<right){
mid = left+(right-left)/2;
if(nums[mid]<target){
left = mid+1;
}else{
right = mid;
}
}
if(nums[left] < target) return right + 1;
return left;
}
}

练习四 : x 的平方根

69. x 的平方根 – 力扣（LeetCode）

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length – 1;
        while (left <= right) {
            int mid = left + (right – left) / 2;
            if (nums[mid] == target) {
                return mid; // 找到目标，返回下标
            } else if (nums[mid] < target) {
                left = mid + 1; // 目标在右侧
            } else {
                right = mid – 1; // 目标在左侧
            }
        }
        // 循环结束没找到，left 就是插入位置
        return left;
    }
}