DenCT/test-storage / DSA Notes /Binary Search.md
DenCT's picture
|
download
raw
8.48 kB
metadata
tags:
  - notes
  - binary-search

Search in 2D Matrix MEDIUM

You are given an m x n 2-D integer array matrix and an integer target.

  • Each row in matrix is sorted in non-decreasing order.
  • The first integer of every row is greater than the last integer of the previous row. Return true if target exists within matrix or false otherwise. Can you write a solution that runs in O(log(m * n)) time? ![[search-in-2d-matrix.png.png]]
Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10
Output: true

![[search-in-2d-matrix-2.png.png]]

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15
Output: false

[!info] Time and Space complexity You should aim for a solution with O(log(m * n)) time and O(1) space, where m is the number of rows and n is the number of columns in the matrix.

Solution

This problem can be solved by two methods:

  1. Finding the element in row and then in the column: Loop over the rows to find the possible location of the target, using binary search technique. Once found, loop over the columns for that row using binary search technique. If found return True else return False.
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])
        
        if target < matrix[0][0] or target > matrix[ROWS - 1][COLS - 1]:
            return False

        row = 0
        top, bottom = row, ROWS - 1
        while top <= bottom:
            row = (top + bottom) // 2
            if target < matrix[row][0]:
                bottom = row - 1
            elif target > matrix[row][-1]:
                top = row + 1
            else:
                break
        
        col = 0
        left, right = col, COLS - 1
        while left <= right:
            mid = (right + left) // 2
            if target == matrix[row][mid]:
                return True
            elif target < matrix[row][mid]:
                right = mid - 1
            elif target > matrix[row][mid]:
                left = mid + 1
        return False
  1. Considering the entire matrix as a flat list: The matrix can be visualised as a flattened 1D sorted array because each row is sorted and every row starts after the previous ends. Using this property, binary search is applied across the entire matrix by converting the 1D mid index into 2D coordinates using row = mid // COLS and col = mid % COLS. This allows efficient comparison with the target in O(log (m × n)) time. No extra space is used, and the search continues by adjusting the binary range based on comparisons until the target is found or the range is exhausted.
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])
        total = ROWS * COLS
        start, end = 0, total - 1
        while start <= end:
            mid = (start + end) // 2
            i = mid // COLS
            j = mid % COLS
            if target == matrix[i][j]:
                return True
            elif target < matrix[i][j]:
                end = mid - 1
            else:
                start = mid + 1
        return False

Koko Eating Bananas MEDIUM

You are given an integer array piles where piles[i] is the number of bananas in the ith pile. You are also given an integer h, which represents the number of hours you have to eat all the bananas. You may decide your bananas-per-hour eating rate of k. Each hour, you may choose a pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, you may finish eating the pile but you can not eat from another pile in the same hour. Return the minimum integer k such that you can eat all the bananas within h hours. Example 1:

Input: piles = [1,4,3,2], h = 9
Output: 2

Explanation: With an eating rate of 2, you can eat the bananas in 6 hours. With an eating rate of 1, you would need 10 hours to eat all the bananas (which exceeds h=9), thus the minimum eating rate is 2. Example 2:

Input: piles = [25,10,23,4], h = 4
Output: 25

[!info] Time and Space Complexity You should aim for a solution with O(nlogm) time and O(1) space, where n is the size of the input array, and m is the maximum value in the array.

Solution

We start with max pile size to be the starting threshold. We calculate the mid threshold between 1 and max pile size and calculate the time taken to complete all piles. We compare the time taken with max provided time h and check if its valid. We continue till we have the ideal threshold.

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        start, end = 1, max(piles)
        threshold = max(piles)
        total = sum(piles)
        while start <= end:
            mid = (start + end) // 2
            time = 0
            for pile in piles:
                time += math.ceil(float(pile) / mid)
            if time <= h:
                threshold = mid
                end = mid - 1
            else:
                start = mid + 1
        return threshold 

Find Minimum in Rotated Sorted Array MEDIUM

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

  • [3,4,5,6,1,2] if it was rotated 4 times.
  • [1,2,3,4,5,6] if it was rotated 6 times. Notice that rotating the array 4 times moves the last four elements of the array to the beginning. Rotating the array 6 times produces the original array. Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array. A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time? Example 1:
Input: nums = [3,4,5,6,1,2]
Output: 1

Example 2:

Input: nums = [4,5,0,1,2,3]
Output: 0

Example 3:

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

[!info] Time and Space Complexity You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.

Solution

class Solution:
    def findMin(self, nums: List[int]) -> int:
        start, end = 0, len(nums) - 1
        res = float("inf")
        while start <= end:
            if nums[start] < nums[end]:
                res = min(res, nums[start])
                break
            mid = (start + end) // 2
            res = min(res, nums[mid])
            if nums[mid] < nums[end]:
                end = mid - 1
            else:
                start = mid + 1
        return res

First Bad Version EASY

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Solution

We start from the mid of the version list. If we find a version that is bad, we flag it and shrink the search space.

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        start, end = 1, n
        bad = float("inf")
        while start <= end:
            mid = (start + end) // 2
            if isBadVersion(mid):
                bad = mid
                end = mid - 1
            else:
                start = mid + 1
        return bad

Xet Storage Details

Size:
8.48 kB
·
Xet hash:
5b7bd122ff83ee267efb72fd954746502df71c328937f5b992564ed6f9105446

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.