LeetCode: Search in Rotated Sorted Array Solution

Approach

Case when

is sorted

• if
  target
  is in the range, decrease
  end
  , otherwise increase
  begin

Case when

is sorted

• if
  target
  is in the range, increase
  begin
  , otherwise decrease
  end

Implementation

1var search = function (nums, target) {
2  let n = nums.length
3  let [begin, end] = [0, n - 1]
4  let res = -1
5
6  while (begin <= end) {
7    let mid = Math.floor((begin + end) / 2)
8
9    if (nums[mid] === target) {
10      res = mid
11      break
12    }
13
14    if (nums[begin] <= nums[mid]) {
15      if (nums[begin] <= target && target <= nums[mid]) {
16        end = mid - 1
17      } else {
18        begin = mid + 1
19      }
20    } else {
21      if (nums[mid] <= target && target <= nums[end]) {
22        begin = mid + 1
23      } else {
24        end = mid - 1
25      }
26    }
27  }
28
29  return res
30}

References

Original problem

Similar problems

Search in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array

Pour Water Between Buckets to Make Water Levels Equal