二分查找

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int left = 0;
  4.         int right = nums.length-1;
  5.         int mid = 0;
  6.         while(left<=right) {
  7.             mid = (left+right)>>1;
  8.             if(target < nums[mid]) {
  9.                 right = mid-1;
  10.             }else if(target > nums[mid]) {
  11.                 left = mid+1;
  12.             }else {
  13.                 return mid;
  14.             }
  15.         }
  16.         return -1;
  17.     }
  18. }

以二分查找为模板的题目

1. 旋转数组的最小数字

做了很久,很恶心

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

image.png

  1. class Solution {
  2.     public int minArray(int[] numbers) {
  4.         int left = 0,right=numbers.length-1;
  5.         int mid= 0;
  6.         while(left<=right) {
  7.             mid = (left+right)>>1;
  8.             if(numbers[mid] < numbers[right]) {
  9.                 right = mid;
  10.             } else if (numbers[mid] > numbers[right]) {
  11.                 left = mid+1;
  12.             } else {
  13.                 right-=1;
  14.             }
  15.         }
  16.         return numbers[left];
  17.     }
  18. }