LeetCode: Search in Rotated Sorted Array Solution

Approach

Case when nums[begin, mid] is sorted

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

Case when nums[mid + 1, end] 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