33. Search in Rotated Sorted Array.md

33. Search in Rotated Sorted Array

---

Difficulty : Medium

Related Topics : Array、Binary Search

---

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is guranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

---

Solution

• Java
  • mine

    • got from the most votes Runtime: 0 ms, faster than 100.00%, Memory Usage: 39 MB, less than 28.30% of Java online submissions

      public int search(int[] nums, int target) {
          int len = nums.length;
          int s = 0, e = len - 1;
          while (s < e) {
              int mid = (s + e) / 2;
              if (nums[mid] > nums[e]){
                  s = mid + 1;
              }else {
                  e = mid;
              }
          }
          int dx = s;
          s = 0;
          e = len - 1;
          while (s <= e) {
              int mid = (s + e) / 2;
              int t = (mid + dx) % len;
              if (nums[t] > target) {
                  e = mid - 1;
              } else if (nums[t] < target) {
                  s = mid + 1;
              } else {
                  return t;
              }
          }
          return -1;
      }
      

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 38.2 MB, less than 22.09% of Java online submissions

      // O(logN)time
      // O(1)space
      public int search(int[] nums, int target) {
          int n = nums.length;
          int l = 0; int r = n - 1;
          while(l <= r){
              int mid = (l + r) >>> 1;
              if(nums[mid] == target){
                  return mid;
              }
              if(nums[mid] < nums[r]){
                  if(target < nums[mid] || target > nums[r]){
                      r = mid - 1;
                  }else{
                      l = mid + 1;
                  }
              }else {
                  if(target < nums[mid] && target >= nums[l]){
                      r = mid - 1;
                  }else{
                      l = mid + 1;
                  }
              }
          }
          return -1;
      }
      

---

• the most votes

• Runtime: 0 ms, faster than 100.00%, Memory Usage: 38.8 MB, less than 33.96% of Java online submissions

  // O(logN)time
  // O(1)space
  public int search(int[] nums, int target) {
      int lo = 0, hi = nums.length;
      while (lo < hi) {
          int mid = (lo + hi) / 2;
          
          double num;
          if ((nums[mid] < nums[0]) == (target < nums[0])) {
              num = nums[mid];
          } else {
              num = target + (target < nums[0] ? -1 : 1);
          }
          if (num < target) {
              lo = mid + 1;
          } else if (num > target) {
              hi = mid;
          } else {
              return mid;
          }
      }
      return -1;
  }
  

• Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.1 MB, less than 25.79% of Java online submissions

  //O(logN)time O(1)space
  int search(int[] A, int target) {
      int n = A.length;
      int lo = 0, hi = n - 1;
      // find the index of the smallest value using binary search.
      // Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
      // Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
      while (lo < hi) {
          int mid = (lo + hi) / 2;
          if (A[mid] > A[hi]) lo = mid + 1;
          else hi = mid;
      }
      // lo==hi is the index of the smallest value and also the number of places rotated.
      int rot = lo;
      lo = 0;
      hi = n - 1;
      // The usual binary search and accounting for rotation.
      while (lo <= hi) {
          int mid = (lo + hi) / 2;
          int realmid = (mid + rot) % n;
          if (A[realmid] == target) return realmid;
          if (A[realmid] < target) lo = mid + 1;
          else hi = mid - 1;
      }
      return -1;
  }
  

---