Searching a Rotated Sorted Array Javascript Solution.

Entry #2

If you recall in my last post find the maximum consecutive ones, we implemented an efficient algorithm to find the longest sequence of consecutive ones in an array. The specification of the question confined us to using linear search to solve this challenge. But as efficient engineers, we found a way to improve the running time of this algorithm by some fraction. Please read the blog post.

Today we'd be attempting to solve another search related algorithm challenge. What's unique about this question is that we are not confined to using any particular search algorithm and so we have the autonomy of choosing any algorithm we feel may solve this challenge efficiently.

Domain problem

Given a rotated sorted array and a target value, find the index of the target value in the array. Return -1 if not found. All items are unique.

example

• input: ([4,5,6,7,1,2,3] 4)
• output: 0

If you'd like to jump straight to the solution, please click here

Solution

If you're like me, your first approach to solving this problem might be to jump straight into it.... tsk.. CALM DOWN!!.

If there's anything I've gained over the last couple of weeks attempting algorithm questions. Always understand the problem very very well before jumping right in.

In your rush to solve this problem, you might want to use a linear search implementation to solve this. Yes, you would definitely get the answer, but imagine you had input with a capacity of over 1000000, the running time of your algorithm becomes O(n). So you might be asking how do we solve this problem and improve the running time of our algorithm? The answer is with another popular search algorithm but before we dive into the specifics, let's understand the problem.

• We know for sure that the array would always be sorted.

• We can also infer that for some given input, the left and right side may be less than the item found in the midpoint of the array.
  -- ([10,11,12,13,2,3,4,5]): 10-12 is less than 13 and 2-5 is less than 13.

  -- [9,1,2,3,4,5,6,7,8]: 9 is greater than 4 but other items are not greater than 4. 5-8 is greater than 4.

Think of this problem as though you were given two sorted arrays, and you were told to make the array with the highest values first and lowest values second. For the second example above, [1...8], [9]. Array with item 9 is greater than all values in first input so it comes first.

Moving on, because we know the array would always be sorted, we can also conclude that some part of the subarray would always be sorted we just need to find out the starting and endpoint of the subarray.

• ([10,11,12,13,2,3,4,5])- first subarray [10,11,12,13] second [2,3,4,5].

Tackling the beast.

Now that we understand the problem, it's time to think of an efficient way to solve the challenge. One very good search algorithm that works well when we have sorted items is the popular binary search. We can use binary search to solve this challenge which would improve our running time from O(n) to O(logn). But given that the array isn't completely sorted, our solution must take into consideration working with the sorted part of the inputs, i.e sorted subarrays. Let's get into attack formation.

SIDENOTE

Before you proceed, you may be wondering why I am not using Javascript array built-in methods like findIndex to solve this. My personal opinion is that as Javascript, we take for granted the superpowers javascript equips us with. As Engineers, we must not only know how to use these superpowers, we must also understand how they work or how the concepts that govern them work. This ensures that we can easily transfer the understanding to other Engineers or Junior Engineers and also efficiently solve problems with these concepts in other languages that don't equip us with Tony Stark Iron man suit. Lastly, the interviewer isn't only assessing your understanding of the language, but also your approach to solving problems. Going all out and solving this without the javascript superpowers gives you an opportunity to show the interviewer your approach to solving problems. You could now take it up a notch buy also stating that the problem could also be solved using an array built-in method like findIndex. So onward we proceed.

Steps

1. define two variables e.g (left and right), left initialized to 0 and right initialized to index of the last item in the array (array length - 1).

2. find the midpoint of the array by adding left and right and dividing it by 2. Round it down to a whole number.

3. If the item at the midpoint is equal to the target value, return midpoint value.

4. Else if the item at the midpoint is greater than the first item in the array, it means the first sorted subarray is between left and midpoint.

4.1. Then if the target value is greater than equal to the left item and less than equal to the midpoint, it means our target value is between left and midpoint, set right to midpoint - 1. Else if it isn't, set left to midpoint + 1.

1. Else the item at the midpoint is less than the first item in the array, meaning the second subarray holds the midpoint of the input.

5.1. If the target is greater than equal to the midpoint item but less than equal to the right item, it means the target value is between the midpoint and right so set left to midpoint + 1; Else if it isn't, set right to midpoint - 1;

1. Repeat starting from step 2 until left is greater than right.

7 . Return -1

const rotatedSortedArraySearch = (nums, target) => {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    let mid = Math.floor((right + left) / 2);

    if (nums[mid] === target) {
      console.log(mid);
      return mid;
    } else if (nums[mid] >= nums[left]) {
      if (target >= nums[left] && target <= nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (target >= nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  console.log(-1);
  return -1;
};

//test cases
rotatedSortedArraySearch([9, 1, 2, 3, 4, 5, 6, 7, 8], 12);
rotatedSortedArraySearch([9, 1, 2, 3, 4, 5, 6, 7, 8], 9);
rotatedSortedArraySearch([], 1);

Conclusion

This was a very tricky problem for me. How would you have solved this problem? Could I do it better? I'd like to hear from you.