二分查找

开平方：https://leetcode-cn.com/problems/sqrtx/submissions/

class Solution {
 public int mySqrt(int x) {

     //双指针
     int left = 1;
     int right = x;

     while(left <= right){
         int middle = left + (right - left)/2;
         //开平方为x/middle
         int sqrt = x/middle;

         //如果sqrt == middle，说明是平方根，返回middle
         if(sqrt == middle){
             return sqrt;
         }else if(sqrt < middle){
             right = middle-1;
         }else if(sqrt > middle){
             left = middle+1;
         }
     }
     return right;
 }
}

旋转数组的最小值：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/submissions/

class Solution {
 public int findMin(int[] nums) {

     int left = 0;
     int right = nums.length-1;
     while(left <= right){
         int middle = left + (right - left)/2;
         //右边比middle大，说明在右半数组，最小值在[middle,right]之间，右边界收缩到middle。
         if(nums[middle] < nums[right]){
             right = middle;
         }else{
             left = middle+1;
         }
     }
     return nums[right];
 }
}

搜索旋转数组的最小值(有重复)：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/submissions/

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

旋转数组搜索target：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

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

         if(nums[middle] < nums[right]){
             //右半，从middle到target和target到right
             if(nums[middle] < target && target <= nums[right]){
                 left = middle+1;
             }else{
                 right = middle-1;
             }
         }else{
             //左半，从left到target和target到middle
             if(nums[left] <= target && target < nums[middle]){
                 right = middle-1;
             }else{
                 left = middle+1;
             }
         }
     }
     return -1;
 }
}

旋转数组搜索target(有重复)：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/

class Solution {
 public boolean search(int[] nums, int target) {
     int left = 0;
     int right = nums.length-1;
     while(left <= right){
         int middle = left + (right - left)/2;
         if(nums[middle] == target){
             return true;
         }
         if(nums[middle] == nums[left] && nums[left] == nums[right]){
             left++;
             right--;
         }else if(nums[middle] <= nums[right]){
             if(nums[middle] < target && target <= nums[right]){
                 left = middle+1;
             }else{
                 right = middle-1;
             }
         }else{
             if(nums[left] <= target && target < nums[middle]){
                 right = middle-1;
             }else{
                 left = middle+1;
             }
         }
     }
     return false;
 }
}