Press "Enter" to skip to content

Posts tagged as “binary search”

LeetCode 74. Search a 2D Matrix (javascript)

By stone on April 12, 2021

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

Solution 1: (DFS)

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    return dfs(matrix, target, 0, 0);
};

function dfs(matrix, target, x, y) {
    let rows = matrix.length;
    let cols = matrix[0].length;
    
    // exit recursion condition, reach to the end;
    if (y === rows) return false;
    
    // traverse from left to right, then next row
    let nextX = (x + 1) % cols;
    let nextY = nextX === 0 ? y + 1 : y;

    // found return true or not found, DFS next element
    if (matrix[y][x] === target) 
        return true;
    else
        return dfs(matrix, target, nextX, nextY);

    return false;
}

Solution 2: (Binary Search) Better and Faster!

  • Time complexity: O(log(mn))
  • Space complexity: O(1)
var searchMatrix = function(matrix, target) {
    let cols = matrix[0].length;
    // 	treat 2D as 1D, use binary search
    let l = 0;
    let r = matrix.length * cols;
    while (l < r) {
        let mid = l + Math.floor((r - l) / 2);
        let row = Math.floor(mid / cols);
        let col = mid % cols;
        if (matrix[row][col] === target) {
            return true;
        } else if (matrix[row][col] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return false;
};

LeetCode 35. Search Insert Position (javascript)

By stone on April 10, 2021

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

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

Example 4:

Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:

Input: nums = [1], target = 0
Output: 0

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums contains distinct values sorted in ascending order.
  • -104 <= target <= 104

Idea:

Use Binary Search

  • Time complexity: O(logn)
  • Space complexity: O(1)

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let l = 0;
    let r = nums.length;
    
    while (l < r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
};

LeetCode 34. Find First and Last Position of Element in Sorted Array (javascript)

By stone on April 2, 2021


Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109

Idea:

Binary Search

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let leftBound = -1;
    let rightBound = -1;
    let l = 0;
    let r = nums.length - 1;
    
    while (l <= r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) {
            leftBound = mid;
            r = mid - 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    l = 0;
    r = nums.length - 1;
    while (l <= r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) {
            rightBound = mid;
            l = mid + 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return [leftBound, rightBound];
};

LeetCode 33. Search in Rotated Sorted Array (javascript)

By stone on March 31, 2021

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). 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].

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

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is guaranteed to be rotated at some pivot.
  • -104 <= target <= 104

Idea:

Binary Search: the idea is to create a recursive function that takes l and h as range in input and the key.

1) Find middle point mid = (l + h)/2
2) If key is present at middle point, return mid.
   Edge case check(not found): if (l > h) return -1;
3) Else If nums[l..mid] is sorted
    a) If key to be searched lies in range from nums[l]
       to nums[mid], recur for nums[l..mid].
    b) Else recur for nums[mid+1..h]
4) Else (nums[mid+1..h] must be sorted)
    a) If key to be searched lies in range from nums[mid+1]
       to nums[h], recur for nums[mid+1..h].
    b) Else recur for nums[l..mid]

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    return searching(nums, 0, nums.length - 1, target);
};

function searching(nums, l, h, target) {
    // basic case: not found
    if (l > h) return -1;
    
    let mid = Math.floor((l + h) / 2);
    // basic case: found
    if (target === nums[mid]) return mid;
    
    // if nums[l...mid] is sorted
    if (nums[l] <= nums[mid]) { /// make sure is <=
        if (target >= nums[l] && target <= nums[mid])
            return searching(nums, l, mid - 1, target);
        else
            return searching(nums, mid + 1, h, target)
    }
    
    // if nums[l...mid] is notesorted, then nums[mid+1..h] must be sorted
    if (target >= nums[mid] && target <= nums[h])
        return searching(nums, mid + 1, h, target);
    else
        return searching(nums, l, mid - 1, target);
}