이진 탐색 (Python Algorithm Interview 18장)

algorithm

파이썬 알고리즘 인터뷰 18장을 정리한 내용입니다.

이진 검색

Binary Search(이진 검색)이란 정렬된 배열에서 타겟을 찾는 검색 알고리즘이다.

  • 이진 검색은 값을 찾아내는 시간 복잡도가 $O(\log n)$ 이라는 점에서 대표적인 로그 시간 알고리즘이며, 이진 탐색 트리와 유사한 점이 많다
  • 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 “자료구조” 라면 이진 검색은 정렬된 배열에서 값을 찾아내는 “알고리즘” 자체를 말한다
1
2
3
4
import math
math.log2(100000000)

'''26.575424...'''
  • 1억개의 아이템도 27번이면 모두 찾아낼 수 있다

이진 검색 예시

1
array = [2, 4, 9, 15, 26, 28, 31]
  • 이진 검색을 이용해서 9 를 찾아볼 것이다
  • 배열은 오름차순으로 정렬되어 있다.

Step 1

  • 임의의 값인 15 를 선택한다
  • 찾을 값과 선택한 값을 비교한다 (9 < 15)
  • 찾을 값은 15 를 기준으로 왼쪽에 있다는 것을 알 수 있다

Step 2

  • 15 를 기준으로 왼쪽에 있는 배열을 다시 탐색한다
  • 임의의 값인 4 를 선택한다
  • 찾을 값과 선택한 값을 비교한다 (4 < 9)
  • 찾을 값은 선택한 값 오른쪽에 위치한다

Step 3

  • 4 를 기준으로 오른쪽에 있는 배열을 정렬한다
  • 찾을 값 9 만 존재하며 원하는 값을 찾았다

이진 검색 종료

#65 이진 검색

정렬된 nums를 받아 이진 검색으로 target에 해당하는 인덱스를 찾아라

입력

1
2
3
4
nums = [-1, 0, 3, 5, 9, 12]
target = 9

# answer = 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def search(nums: list, target: int) -> int:
    def binary_search(left, right):
        if left <= right:
            mid = (left + right) // 2

            if nums[mid] < target:
                return binary_search(mid + 1, right)
            elif nums[mid] > target:
                return binary_search(left, mid - 1)
            else:
                return mid
        else:
            return -1
    return binary_search(0, len(nums) - 1)
  • 재귀로 이진 검색을 구현한 것이다
  • 절반씩 범위를 줄여나가면서 맞을 때까지 재귀 호출을 한다

반복 풀이

1
2
3
4
5
6
7
8
9
10
11
12
def BS(nums: list, target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2

        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            return mid
    return -1

이진 검색 모듈

1
2
3
4
5
6
7
def moduleSearch(nums: list, target: int) -> int:
    index = bisect.bisect_left(nums, target)

    if index < len(nums) and nums[index] == target:
        return index
    else:
        return -1
  • 파이썬에 이진 검색 모듈을 이용해서 풀 수 있다
  • bisect 모듈은 이진 검색 알고리즘이다

이진 검색을 사용하지 않는 index 풀이

1
2
3
4
5
def NotIndex(nums: list, target: int) -> int:
    try:
        return nums.index(target)
    except ValueError:
        return -1
  • 파이썬에서 제공하는 해당 값의 인덱스를 찾아내는 index() 메소드를 활용한다
  • 존재하지 않는 값이면 에러가 발생하기 때문에 예외처리를 해준다
  • 이 코드는 이진 검색이 아니며 이진 검색을 요구하는 문제에는 사용하면 안된다

#66 회전 정렬된 배열 검색

특정 피벗을 기준으로 회전하여 정렬된 배열에서 target 값의 인덱스를 출력하라

입력

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

피벗을 기준으로 한 이진 검색

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def search(nums: list, target: int) -> int:
    if not nums:
        return -1

    # 최솟값을 찾기
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    pivot = left

    # 피벗 기준 이진 검색
    left, right = 0, len(nums)
    while left <= right:
        mid = left + (right - left) // 2
        mid_pivot = (mid + pivot) % len(nums)

        if nums[mid_pivot] < target:
            left = mid + 1
        elif nums[mid_pivot] > target:
            right = mid - 1
        else:
            return mid_pivot

    return -1

#67 두 배열의 교집합

두 배열의 교집합을 구하라

입력

1
2
num1 = [1, 2, 2, 1]
num2 = [2, 2]

이진 검색으로 일치 여부 판별

1
2
3
4
5
6
7
8
9
def intersection(num1: list, num2: list) -> set:
    res = set()
    num2.sort()
    for n1 in num1:
        #  이진 검색으로 일치 여부 판별
        i2 = bisect.bisect_left(num2, n1)
        if len(num2) > 0 and len(num2) > i2 and n1 == num2[i2]:
            res.add(n1)
    return res
  • 한쪽은 순서대로 탐색, 다른쪽은 정렬해서 이진 검색으로 값을 찾는다
  • num2 를 정렬한 상태에서 num1 을 순차 반복하면서 num2 를 이진 검색 한다

투 포인터로 일치 여부 판별

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def intersectioin_two_pointer(num1: list, num2: list) -> set:
    res = set()
    num1.sort()
    num2.sort()
    i = j = 0
    # 투 포인터 우측으로 이동하며 일치 여부 판별
    while i < len(num1) and j < len(num2):
        if num1[i] > num2[j]:
            j += 1
        elif num1[i] < num2[j]:
            i += 1
        else:
            res.add(num1[i])
            i += 1
            j += 1
    return res
  • 각각의 입력받은 리스트를 정렬한다
  • 값이 작은 쪽 배열 포인터가 한 칸씩 앞으로 이동하는 형태이고 어느 한쪽의 포인터가 끝까지 도달하면 종료하게된다

#68 두 수의 합

정렬된 배열을 받아 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라 (배열의 시작은 1로 한다)

입력

1
2
numbers = [2, 7, 11, 15]
target = 9

투 포인터

1
2
3
4
5
6
7
8
9
def twoPointer(number: list, target: int) -> list:
    left, right = 0, len(number) - 1
    while not left == right:
        if number[left] + number[right] < target:
            left += 1
        elif number[left] + number[right] > target:
            right -= 1
        else:
            return [left + 1, right + 1]

bisect 모듈

1
2
3
4
5
6
7
def bisect_slicing(number: list, target: int) -> list:
    for k, v in enumerate(number):
        expected = target - v
        nums = number[k + 1]
        i = bisect.bisect_left(nums, expected)
        if i < len(nums) and number[i + k + 1] == expected:
            return [k + 1, i + k + 2]

#69 2D 행렬 검색

mxn 행렬에서 값을 찾아내는 효율적인 알고리즘을 구현하라. 행렬은 왼쪽에서 오른쪽, 위에서 아래 오름차순으로 정렬되어 있다

/images/img/posts/pyAlgo/chapter18/pic.png

첫 행의 맨 뒤에서 탐색

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def searcgMatrix(matrix: list, target: int) -> bool:
    if not matrix:
        return False

    # 첫 행의 맨 뒤
    row = 0
    col = len(matrix[0]) - 1

    while row <= len(matrix) - 1 and col >= 0:
        if target == matrix[row][col]:
            return True
        elif target < matrix[row][col]:
            col -= 1
        elif target > matrix[row][col]:
            row += 1
    return False
  • 첫 행의 맨 뒤 요소를 선택하고 타겟이 더 작으면 왼쪽으로, 크면 아래로 이동한다

파이썬 다운 방식

1
2
def searchMat(matrix, target):
    return any(target in row for row in matrix)
  • 행렬에 값이 존재하는지 여부를 위에서부터 차례로 한 줄씩 탐색한다