Leetcode Search in Rotated Sorted Array

Question

I was doing Search in sorted array question from leetcode

Question

Suppose an array sorted in ascending order 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]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example

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

My solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    for (let i=0; i<nums.length; i++) {
        if (target === nums[i]) return i
    }
    return -1 
};

While this algo works, I am not sure if this is optimal or correct? for question with medium difficulty. Can someone verify it?

Answer 1

I start from your code:

var search = function(nums, target) {
    for (let i=0; i<nums.length; i++) {
        if (target === nums[i]) return i
    }
    return -1 
};

And your question:

While this algo works, I am not sure if this is optimal or correct?

Your algorithm is correct but it is optimal ? The answer is nope because as from the comment by @CertainPerformance to your question your code runs in O(n).

The hint is contained in the phrase Your algorithm's runtime complexity must be in the order of O(log n) that bounds the desired solution to the binary search having O(log n) complexity. The algorithm works if there is a sorted array, but with some modification can be adapted to a rotated array.

Here my javascript code for the original binary search:

const search = function search(a, t) {
    let l = 0;
    let r = a.length - 1;

    while (l <= r) {
        let m = Math.floor((l+r) /2);
        if (a[m] == t) { return m;  }
        if (a[m]  < t) { l = m + 1; }
        if (a[m]  > t) { r = m - 1; } 
   }
   return -1;
}

My solution for a rotated array is quite similar but with a two if else inside the while cycle because we can have four different cases, I added an explanation after the code below:

const search = function search(a, t) {
    let l = 0;
    let r = a.length - 1;

    while (l <= r) {
        let m = Math.floor((l+r) /2);
        if (a[m] == t) { return m; }

        if (a[m] < a[r]) {
            if (t > a[m] && t <= a[r]) { 
                l = m + 1; 
            } else { 
                r = m - 1; 
            }
        } else {
            if (t >= a[l] && t < a[m]) { 
                r = m - 1; 
            }
            else {
                l = m + 1;
            }
        }
    }

    return -1;
}

console.log(search([4,5,6,7,0,1,2], 0));
console.log(search([4,5,6,7,0,1,2], 5));
console.log(search([4,5,6,7,0,1,2], 3));
console.log(search([1, 3], 3));
console.log(search([4,5,6,7,8,1,2,3], 8));

Substantially if I have a [l,..m, .. r] interval I have two possible cases:

1. a[m] < a[r] --> consecutive ascending numbers, so if a[m] < t <= a[r] in the next iteration I will examine the interval [m + 1, r] otherwise I will examine the interval [l, r - 1]
2. a[m] >= a[r] --> there are rotated elements like for example [7, 0, 1, 2] , so I am sure the left array contains only ascending numbers. In this case if a[l] <= a[t] < a[m] in the next iteration I will examine the interval [l, m - 1] otherwise I will examine the interval [m + 1, r].