Implicitly Sorted Array

This technique uses an efficient way to find a certain element in a implicitly sorted array, linked list, or matrix.

How to Identify

• Data Structure Involves: Array, Linked list, or Matrix
• Question Type: When you need to find a certain element in a implicitly sorted data structure.

Example

Search in Rotated Sorted Array

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]

Example

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

Typescript

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

    while(left <= right){
        const mid = Math.floor((left+right)/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
}

Related Problems

	Problems	Difficulty
1	Search in Rotated Sorted Array	Medium
2	Find Minimum in Rotated Sorted Array	Medium
3	Find Peak Element	Medium