[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; } }

算法原理 :

1. 数组必须有序
2. 每次取中间位置 , 和目标位置比较
3. 比目标小->去右边找
4. 比目标大->去左边找
5. 直到找到或找不到

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

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)

注意 :

1. 循环条件 : left<right

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

1. 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;     } }