[파이썬 알고리즘 인터뷰] 이진 검색

• 이진 검색: 정렬된 배열에서 타겟을 찾는 검색 알고리즘
  • 값을 찾아내는 시간 복잡도가 O(logn)

704. Binary Search

- 재귀로 이진 검색

* 파이썬은 재귀 호출 횟수 제한이 1000번으로 정해져있으므로 유의 (sys 모듈로 변경가능하지만 대부분 지원하지 않음)

- 반복으로 이진 검색

- 이진 검색 모듈 bisect

- index()

* 최악의 경우 O(n)으로, 앞에서부터 탐색하므로 뒤에 위치할수록 느려진다

• bisect.bisect(iterable, value)는 bisect.bisect_right(iterable, value)와 같으며 value 값이 iterable에 정렬되어 삽입된다면 위치할 인덱스 값 리턴 -> value 값과 동일한 값이 이미 iterable에 있다면 그 값 우측에 위치
• bisect.bisect_left(iterable, value)
• bisect.insort(iterable, value)는 value를 실제 iterable에 정렬되게 삽입

# 중앙값 인덱스 계산
mid = (left + right) // 2
# 자료형에는 최댓값이 존재하기 때문에 left + right > int의 최댓값(2^31 - 1) 일때 오버플로우
# 파이썬은 해당 문제에서 자유롭지만 자료형이 엄격한 언어들에서는 유의해야함
mid = left + (right - left) // 2

 

33. Search in Rotated Sorted Array

- 이진 검색으로 피벗 인덱스 찾고, 이진 검색으로 정답 추출

- 내 풀이: 정답 인덱스 찾을 때 bisect 모듈 이용

• 맨 좌우측에 있는 포인터(left, right) 중 어떤 포인터를 mid에 위치해 절반씩 범위를 줄여나갈지 고민

# 리트코드에서 또 다른 답안
# 피벗 찾지 않고 바로 타겟 위치 검색
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if (nums[0] <= target < nums[mid] or
                nums[mid] < nums[0] and not
                nums[mid] < target < nums[0]):
                r = mid - 1
            else:
                l = mid + 1
                
        return -1

 

349. Intersection of Two Arrays

- 브루트 포스 -> O(n^2)

- 이진 검색 -> 한쪽은 순차 탐색, 다른 쪽은 정렬 후 이진 탐색 O(nlogn)

- 투 포인터 -> 두 배열 정렬 후 각각 포인터를 앞에서부터 순차적으로 이동하면서 값 비교 O(nlogn)

- 내 풀이: set intersection (&)

 

167. Two Sum II - Input Array Is Sorted

- 투 포인터

- 이진 검색

- bisect + 슬라이싱

- bisect + 슬라이싱 최소화

• 매우 긴 배열은 슬라이싱으로도 상당한 시간이 소요되므로 주의 필요

- bisect.bisect_left의 세번째 파라미터로 탐색할 배열의 왼쪽 범위 제한

- 내 풀이: bisect.bisect_right 활용

• 탐색할 배열에서 찾는 요소가 중복될 때
  • bisect.bisect_left는 중복되는 요소들 중 첫 요소의 인덱스 반환
  • bisect.bisect_right는 중복되는 요소들 중 마지막 요소 다음 인덱스 반환
• bisect.bisect_left(iterable, value, lo, hi)에서 lo, hi는 각각 탐색할 배열의 시작과 끝 인덱스 (bisect.bisect_right 동일)

240. Search a 2D Matrix II

- 첫 행의 맨 끝 요소에서 탐색 -> 타겟과 비교하여 타겟이 작으면 왼쪽으로 한칸, 크면 아래로 한칸 이동

- any()

- 내 풀이: 행은 순차적으로 돌면서 각 행 내부적으로는 이분 탐색

• any()는 포함된 값 중 어느 하나가 참이면 참으로 출력
• all()은 모든 값이 참이어야 참으로 출력