leetcode-javascript/solutions/0081-search-in-rotated-sorted-array-ii.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Search In Rotated Sorted Array II
 * Time Complexity: O(N)
 * Space Complexity: O(1)
 */
var search = function (nums, target) {
  let startBoundary = 0;
  let endBoundary = nums.length - 1;

  while (startBoundary <= endBoundary) {
    let currentMiddle =
      startBoundary + Math.floor((endBoundary - startBoundary) / 2);

    if (nums[currentMiddle] === target) {
      return true;
    }

    if (
      nums[startBoundary] === nums[currentMiddle] &&
      nums[currentMiddle] === nums[endBoundary]
    ) {
      startBoundary++;
      endBoundary--;
      continue;
    }

    if (nums[startBoundary] <= nums[currentMiddle]) {
      if (nums[startBoundary] <= target && target < nums[currentMiddle]) {
        endBoundary = currentMiddle - 1;
      } else {
        startBoundary = currentMiddle + 1;
      }
    } else {
      if (nums[currentMiddle] < target && target <= nums[endBoundary]) {
        startBoundary = currentMiddle + 1;
      } else {
        endBoundary = currentMiddle - 1;
      }
    }
  }

  return false;
};