Search in Rotated Sorted Array

Leetcode Problem 33: Search in Rotated Sorted Array

Problem Summary

An ascending array of distinct integers has been possibly rotated at an unknown index, resulting in an array like [4,5,6,7,0,1,2] (rotated from [0,1,2,4,5,6,7]). Given this rotated array and a target, return the index of the target if it exists, or -1 otherwise.

Your solution must run in O(log n) time.

Constraints:

• The array has between 1 and 5,000 elements, all distinct.
• Element values and the target are integers in the range [-10,000, 10,000].

Techniques

• Array
• Binary Search

Solution

import * as sea from "node:sea";

function search(nums: number[], target: number): number {
    let left = 0
    let right = nums.length - 1

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

        if (nums[mid] === target) {
            return mid
        }

        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left  = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return -1
}

console.log(search([4,5,6,7,0,1,2], 0)) // Output: 4