leetcode 33. Search in Rotated Sorted Array

理解数组长成什么样是非常重要

function search(nums, target) {
      var left = 0, right = nums.length - 1;
      while (left <= right) {
        var mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
          return mid;
        } else if (nums[mid] < nums[right]) {
          // [ 1, 2, 3 4, 5,6,7,8], target = 5， mid = 4
          // target在 5～8找
          if (nums[mid] < target && nums[right] >= target) {
            left =  mid + 1;
          } else { // target = 2， mid = 4
            right = mid - 1;
          }
        } else {//[6 7 8 9 10 11 0，1，2，3  ],  target = 7, mid = 11
          if (nums[left] <= target && nums[mid] > target) {
            right = mid - 1;
          } else {//target = 2, mid = 11
            left = mid + 1;
          }
        }
      }
      return -1;
    }