Sorted Array

This technique uses an efficient way to find a certain element in a 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 sorted data structure.

Example

Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Example

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Typescript

function search(nums: number[], target: number): number {
    return binarySearch(nums, target, 0, nums.length - 1)
}

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

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

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

    return -1
}

Related Problems

	Problems	Difficulty
1	Binary Search	Easy
2	Search a 2D Matrix	Medium