博客
我作了首诗，保你闭着眼睛也能写对二分查找

最好还是自己想

寻找一个数

  1. int binarySearch(int[] nums, int target) {
  2.     int left = 0; 
  3.     int right = nums.length - 1; // 注意
  5.     while(left < right) {
  6.         int mid = left + (right - left) / 2;
  7.         if(nums[mid] == target)
  8.             return mid; 
  9.         else if (nums[mid] < target)
  10.             left = mid + 1; // 注意
  11.         else if (nums[mid] > target)
  12.             right = mid; // 注意
  13.     }
  14.     return -1;
  15. }

寻找左侧边界

  1.     public int leftBound(int[] nums, int target){
  2.         if(nums.length==0) return -1;
  3.         int l=0;
  4.         int r=nums.length-1;
  5.         while(l<=r){
  6.             int mid=l+(r-l)/2;
  7.             if(nums[mid]<target){
  8.                 l=mid+1;
  9.             }else if(nums[mid]>target){
  10.                 r=mid-1;
  11.             }else{
  12.                 r=mid-1;
  13.             }
  14.         }
  15.         if(l<0||nums[l]!=target) return -1;
  16.         return l;
  17.     }

寻找右侧边界

  1.     public int rightBound(int[] nums, int target){
  2.         if(nums.length==0) return -1;
  3.         int l=0;
  4.         int r=nums.length-1;
  5.         while(l<=r){
  6.             int mid=l+(r-l)/2;
  7.             if(nums[mid]<target){
  8.                 l=mid+1;
  9.             }else if(nums[mid]>target){
  10.                 r=mid-1;
  11.             }else{
  12.                 l=mid+1;
  13.             }
  14.         }
  15.         if(r<0||nums[r]!=target) return -1;
  16.         return r;
  17.     }

剑指 Offer 53 - I. 在排序数组中查找数字 I

剑指 Offer 53 - I. 在排序数组中查找数字 I
找到最左侧下标，向右遍历
注意需要判断返回的下标是否符合要求
比如：
[5,7,7,8,8,10]
6
返回的index=1，但实际上nums[1]=7，不等于6

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int l=0, r=nums.length-1;
  4.         while(l<r){
  5.             int mid=l+(r-l)/2;
  6.             if(nums[mid]>target){
  7.                 r=mid-1;
  8.             }else if(nums[mid]<target){
  9.                 l=mid+1;
  10.             }else{
  11.                 r=mid;
  12.             }
  13.         }
  14.         int count=0;
  15.         for(int i=l;i<nums.length;i++){
  16.             if(nums[i]==target) count++;
  17.             else break;
  18.         }
  19.         return count;
  20.     }
  21. }

搜索旋转排序数组

笔记：https://www.yuque.com/yyruilin/pgtm47/ai74n7