[알고리즘] 이진 검색 binary search

코딩테스트 때 툭 치면 툭 나와야할 알고리즘 코드 스니펫 모음

Binary Search

재귀적 구현

int binarySearch(int[] array, int target) throws BSException{
    return binarySearch(array, target, 0, array.lengh-1);
}

int binarySearch(int[] array, int target, int lower, int upper) throws BSException{
    int center
    int range;

    range = upper - lower;
    if(range < 0){
        throw new BSException("Element not in array");
    }
    if(array[lower] > array[upper]){
        throw new BSException("Array not sorted");
    }

    center = (range / 2) + lower;

    if (target == array[center]){
        return center;
    } else if (target < array[center]) {
        return binarySearch(array, target, lower, center -1);
    } else {
          return binarySearch(array, target, center + 1, upper);
    }
}

반복문

int iterBinarySearch(int[] array, int target) throws BSException{
    int lower = 0;
    int upper = array.lengh -1;
    int center;
    int range;

    while(true){
        range = upper - lower;
        if(range < 0){
            throw new BSException("Element not in array");
        }
        if(array[lower] > array[upper]){
            throw new BSException("Array not sorted");
        }
        center = (range / 2) + lower;
        if(target == array[center]){
            return center;
        } else if (target < array[center]) {
            upper = center - 1;
        } else {
            lower = center + 1;
        }
    }

}

Leetcode 풀이

729. My Calendar I (medium)

binary search 문제인데 실제 풀이는 bisect_left, SortedList 를 이용해 직접 구현하지 않고 풀 수도 있음.

Brute force

class MyCalendar:
    def __init__(self):
        self.booked_list = []

    # N^2
    def book_brute_force(self, start: int, end: int) -> bool:
        # order first
        for i in self.booked_list:
            if i[0] < end and start < i[1]:
                return False
        # add it on the whole booking list, if it's true
        self.booked_list.append([start,end])
        return True

# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)

• time complexity: O(N^2)
• spece complexity: O(N)

binary search

from bisect import bisect_left
from sortedcontainers import SortedList    

class MyCalendar:
    def __init__(self):
        self.booked_list = SortedList()
    '''
    book 
    Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.
    '''

    def book(self, start: int, end: int) -> bool:
        # get index 
        idx = self.booked_list.bisect_left([start,end])
        # [(10, 20) (30, 40), 40, 50], (20, 30) -> 1
        if idx > 0 and self.booked_list[idx-1][1] > start:
            return False
        if idx < len(self.booked_list) and self.booked_list[idx][0] < end:
            return False
        self.booked_list.add([start,end])
        return True

    # binary search implementation

• time complexity: binary search가 N만큼 반복되므로 O(NlogN) bisect에 O(logN), insertion에 O(logN)
• spece complexity: O(N)

binary search 직접 구현

TODO

1885. Count Pairs in Two Arrays

Brute Force (time out)

class Solution:
    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
        # brute force
        # collections.combination
        nCr = itertools.combinations(range(len(nums1)), 2)
        ncr_list = list(nCr)

        result = 0
        for i in ncr_list:
            print(i)
            if nums1[i[0]] + nums1[i[1]] > nums2[i[0]] + nums2[i[1]]:
                result += 1
        return result

Binary Serach

from bisect import bisect_right

class Solution:
    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
        # nums1[i] + nums1[j] > nums2[i] + nums2[j]
        # chagned to 
        # (nums1[i] + nums1[j]) - (num2[i] + nums2[j]) > 0
        # nums1[i] - nums2[i] + nums1[j] - nums2[j]  > 0

        nums = []
        for i in range(len(nums1)):
            nums.append(nums1[i] - nums2[i])

        # now we can sort
        nums.sort()
        # binary search 
        # now it's typical question - finding the number of x > y pairs in a given array
        result = 0
        for i, x in enumerate(nums):
            # lo=i + 1 because you don't wanna compare with the same index
            idx = bisect.bisect_right(nums, -1 * x, lo = i + 1)
            result += len(nums) - idx

        return result

1146. Snapshot Array

### Brute Force 

exceeded time limit

class SnapshotArray:

    def __init__(self, length: int):
        self.array = [0] * length
        self.snap_id = 0
        self.snap_dic = {}

    def set(self, index: int, val: int) -> None:
        self.array[index] = val
        # print(self.array)
        # print(self.snap_dic)

    def snap(self) -> int:
        self.snap_id += 1
        # take a snapshot of array
        input_array = self.array
        self.snap_dic[self.snap_id - 1] = input_array.copy() #array
        # print(self.snap_dic)
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        return self.snap_dic[snap_id][index]


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)