Binary Search

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

Binary Searchは微妙なパターンの違いとかがあってこれまでよりは難しい印象。

easy問題の型を100回くらい書いて覚えるのが最初にやることだと個人的には思う。

そういう意味で、これまでの分野と比較すると覚えることがあるなーという印象。

この後、LinkedListとかGraphsとかでも覚える必要があるアルゴリズムがいくつかあるので、入門としてはちょうど良い気がする。

22. Binary Search

Problem

You are given an array of distinct integers nums, sorted in ascending order, and an integer target.

Implement a function to search for target within nums. If it exists, then return its index, otherwise, return -1.

Your solution must run in O(logn) time.

Example 1:

Input: nums = [-1,0,2,4,6,8], target = 4

Output: 3

Example 2:

Input: nums = [-1,0,2,4,6,8], target = 3

Output: -1

Constraints:

1 <= nums.length <= 10000.

-10000 < nums[i], target < 10000

Solution

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            m = l + (r-l) // 2
            if nums[m] == target:
                return m
            elif nums[m] < target:
                l = m + 1
            else:
                r = m - 1
        
        return -1

23. Search a 2D Matrix

Problem

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?

Example 1:

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

Output: true

Example 2:

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

Output: false

Constraints:

m == matrix.length

n == matrix[i].length

1 <= m, n <= 100

-10000 <= matrix[i][j], target <= 10000

Solution

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])
        t, b = 0, ROWS - 1

        while t <= b:
            c = t + (b-t) // 2
            if matrix[c][0] <= target <= matrix[c][COLS-1]:
                break
            elif target < matrix[c][0]:
                b = c - 1
            else:
                t = c + 1
        
        # この状態になってると、targetが存在しなかったことになる
        if t > b:
            return False
        
        # あとは普通のBinary Search
        l, r = 0, COLS-1
        while l <= r:
            m = l + (r - l) // 2
            if matrix[c][m] == target:
                return True
            elif matrix[c][m] < target:
                l = m + 1
            else:
                r = m - 1
        
        return False
        

24. Koko Eating Bananas

Problem

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

Constraints:

1 <= piles.length <= 1,000

piles.length <= h <= 1,000,000

1 <= piles[i] <= 1,000,000,000

Solution

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        max_pile = max(piles)

        l, r = 1, max_pile
        while l <= r:
            m = l + (r-l) // 2
            
            # m個のバナナを一時間に食べる場合に
            # 全てのpileを消費する時間
            hours = 0
            for p in piles:
                hours += math.ceil(p / m)
            
            if hours == h:
                # ちょうどh時間だったらこれ以上改善できない
                return m
            elif hours < h:
                # 早く食べ終わり過ぎてる場合は
                # もう少しmの値を落としてok
                r = m - 1
            else:
                # hよりも大きい場合は
                # もっとたくさん食べなきゃいけない
                l = m + 1
        

        return l

25. Find Minimum In Rotated Sorted Array

Problem

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

Constraints:

1 <= nums.length <= 1000

-1000 <= nums[i] <= 1000

Solution

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        min_val = math.inf

        while l <= r:
            m = l + (r - l) // 2
            min_val = min(min_val, nums[m])
            if nums[m] <= nums[r]:
                # この場合、最小値はmよりも左側にある
                r = m - 1
            else:
                # この場合、6→1のような切れ目がmとrの間にある
                l = m + 1
            
        return min_val

26. Search In Rotated Sorted Array

Problem

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.

Given the rotated sorted array nums and an integer target, return the index of target within nums, or -1 if it is not present.

You may assume all elements in the sorted rotated array nums are unique,

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], target = 1

Output: 4

Example 2:

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

Output: -1

Constraints:

1 <= nums.length <= 1000

-1000 <= nums[i] <= 1000

-1000 <= target <= 1000

Solution

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            m = l + (r-l) // 2
            if nums[m] == target:
                return m
            elif nums[l] <= nums[m]:
                # lからmまではソートされてる
                if nums[l] <= target < nums[m]:
                    # targetがソートされてる中にあるのでrを内側に動かす
                    r = m - 1
                else:
                    # targetがソートされてる中にないので
                    # lをmの次に動かす
                    l = m + 1
            else:
                # lからmまではソートされてないので、
                # 逆にmからrまでは必ずソートされてる
                if nums[m] < target <= nums[r]:
                    # targetがソートされてる中にあるのでrを内側に動かす
                    l = m + 1
                else:
                    # targetがソートされてる中にないので
                    # rをmの前に動かす
                    r = m - 1
        
        return -1

27. Time Based Key Value Store

Problem

Implement a time-based key-value data structure that supports:

Storing multiple values for the same key at specified time stamps

Retrieving the key's value at a specified timestamp

Implement the TimeMap class:

TimeMap() Initializes the object.

void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.

String get(String key, int timestamp) Returns the most recent value of key if set was previously called on it and the most recent timestamp for that key prev_timestamp is less than or equal to the given timestamp (prev_timestamp <= timestamp). If there are no values, it returns "".

Note: For all calls to set, the timestamps are in strictly increasing order.

Example 1:

Input:

["TimeMap", "set", ["alice", "happy", 1], "get", ["alice", 1], "get", ["alice", 2], "set", ["alice", "sad", 3], "get", ["alice", 3]]

Output:

[null, null, "happy", "happy", null, "sad"]

Explanation:

TimeMap timeMap = new TimeMap();

timeMap.set("alice", "happy", 1); // store the key "alice" and value "happy" along with timestamp = 1.

timeMap.get("alice", 1); // return "happy"

timeMap.get("alice", 2); // return "happy", there is no value stored for timestamp 2, thus we return the value at timestamp 1.

timeMap.set("alice", "sad", 3); // store the key "alice" and value "sad" along with timestamp = 3.

timeMap.get("alice", 3); // return "sad"

Constraints:

1 <= key.length, value.length <= 100

key and value only include lowercase English letters and digits.

1 <= timestamp <= 1000

Solution

from collections import defaultdict

class TimeMap:

    def __init__(self):
        # key -> (value, timestamp)
        self.time_map = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.time_map[key].append((value, timestamp))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.time_map:
            # keyが存在しなければ空文字を返す
            return ''
        
        value_time_array = self.time_map[key]
        # ここでtimestampに最も近い時間のvalueを探す。
        # Binary SearchをやることでO(N)がO(Log N)になる

        res = ''
        l, r = 0, len(value_time_array) - 1
        while l <= r:
            m = l + (r-l) // 2
            if value_time_array[m][1] <= timestamp:
                # もしここに一度も入らなければtmestamp以前の
                # 値が全くないので空文字が勝手に返る
                res = value_time_array[m][0]
                # まだ余裕があるかもしれないのでlを右に動かしてみる
                l = m + 1
            else:
                r = m - 1
        
        return res

28. Median of Two Sorted Arrays

Problem

ou are given two integer arrays nums1 and nums2 of size m and n respectively, where each is sorted in ascending order. Return the median value among all elements of the two arrays.

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

Example 1:

Input: nums1 = [1,2], nums2 = [3]

Output: 2.0

Explanation: Among [1, 2, 3] the median is 2.

Example 2:

Input: nums1 = [1,3], nums2 = [2,4]

Output: 2.5

Explanation: Among [1, 2, 3, 4] the median is (2 + 3) / 2 = 2.5.

Constraints:

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

-10^6 <= nums1[i], nums2[i] <= 10^6

Solution

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 短い方をA, 長い方をBとして、
        # Aの方のポインターを動かして考えていく
        A, B = nums1, nums2
        if len(A) > len(B):
            A, B = B, A
        
        total_len = len(A) + len(B)
        half_len = total_len // 2
        
        l, r = 0, len(A) - 1
        while True:
            m_a = l + (r - l) // 2
            m_b = half_len - m_a - 2

            # 配列Aの中央値以下部分の最大値
            left_A = A[m_a] if m_a >= 0 else -math.inf
            # 配列Aの中央値より大きい部分の最小値
            right_A = A[m_a + 1] if m_a + 1 < len(A) else math.inf

            # 配列Bの中央値以下部分の最大値
            left_B = B[m_b] if m_b >= 0 else -math.inf

            # 配列Bの中央値より大きい部分の最小値
            right_B = B[m_b + 1] if m_b + 1 < len(B) else math.inf
            
            if left_A <= right_B and right_A >= left_B:
                if total_len % 2 == 0:
                    # 全体の長さが偶数の場合はleft_A, left_Bの最大値と
                    # right_A, right_Bの最小値を2で割った数が答え
                    return (max(left_A, left_B) + min(right_A, right_B)) / 2
                else:
                    # 全体の長さが奇数の場合はright_A, right_Bの最小値が答え
                    return min(right_A, right_B)
            elif left_A > right_B:
                r = m_a - 1
            else:
                l = m_a + 1