2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Hello, I have seen the leetcode site and in the description of the challenge you forgot to write the most important information : Your algorithm's runtime complexity must be in the order of O(log n). Please add it to the challenge description. \$\endgroup\$ – dariosicily May 23 at 7:11
  • \$\begingroup\$ @dariosicily done. Also, Isn't the complexity of the above algo 0(log n)? \$\endgroup\$ – iRohitBhatia May 23 at 8:39
  • 1
    \$\begingroup\$ Your code runs in O(n), which is not fulfilling the requirement \$\endgroup\$ – CertainPerformance May 23 at 11:35
1
\$\begingroup\$

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].
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.