목차

• 이진 탐색 Binary Search
  • 정의
  • 알고리즘 개요
  • 수도코드
  • 구현(파이썬)
    • 재귀 구현
    • 반복 구현
    • 이진 검색 모듈 bisect
  • 구현(자바)
  • 이진 검색 알고리즘 버그(자바)

이진 탐색 Binary Search

정의

정렬된 배열에서 타겟을 찾는 검색 알고리즘

• O(\(log_{2}n\))알고리즘
• 대표적인 로그 시간 알고리즘
• 로그는 1억 개의 아이템도 단 27번이면 모두 찾아낼 정도로 설능이 좋음

   >>> import math 
   >>> math.log2(100000000)
   26.575424759098897
  

• 이진 탐색 트리 Binary Search Tree (이하 BST)와도 유사한 점이 많음
• BST(Binary Search Tree): 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 ‘자료구조’
• 이진 검색(Binary Search): 정렬된 배열에서 값을 찾아내는 ‘알고리즘’ 자체를 지칭
• [주의] 같은 Binary Search가 들어가도 둘은 다른 개념이므로 혼동하지 않게 주의

알고리즘 개요

• 정렬된 배열에서 가운데 값과 찾고자 하는 원소를 비교
  • 찾는 값이 더 작으면: 배열의 작은 쪽에서 다시 가운데 값과 비교
  • 찾는 값이 더 크면: 배열의 큰 쪽에서 다시 가운데 값과 비교
• 찾을 때까지 같은 방법을 계속 실행함

ex) 1부터 100까지의 숫자 중 79를 찾는 과정
① 중간값 50부터 탐색을 시작
①-② 79는 50보다 크므로 왼쪽 포인터를 오른쪽으로 이동

② 그다음 중간값 75로 탐색 시작
②-② 79는 75보다 크므로 마찬가지로 왼쪽 포인터를 오른쪽으로 이동

③ 그 다음 중간값 87로 탐색 시작
③-② 79는 87보다는 작으므로 이번에는 오른쪽 포인터를 왼쪽으로 이동
… ⑥ 77=77
-> 이런 식으로 점점 범위를 좁혀 나가면 \(log_{2}100\) 즉, 7번 이내에 무조건 숫자를 맞출 수 있음

>>> math.log2(100)
6.643856189774724

수도코드

정렬된 nums 를 입력받아 이진 검색으로 target 에 해당하는 인덱스를 찾아라.
•입력
nums = [-1,0,3,5,9,12], target = 9
•출력
4

구현(파이썬)

ex) 리트코드 704. Binary Search

재귀 구현

def search(self, nums: List[int], 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)

+) 명시적으로 표현하기 위해 return을 print로 바꿈

[주의] 파이썬 재귀 제한
파이썬에는 재귀 호출에 대한 호출 횟수 제한이 있으며 기본 값은 1,000으로 설정되어 있다.

>>> sys.getrecursionlimit()
1000

반복 구현

• 조금 더 직관적
• 재귀보단 덜 우아함

  def search(self, nums: List[int], 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
  

  

이진 검색 모듈 bisect

파이썬에서는 이진 검색을 직접 구현할 필요가 없음
이진 검색 알고리즘을 지원하는 bisect 모듈을 기본으로 제공.

• 오름차순인 리스트에 쓸 수 있음
• 여러 가지 예외 처리를 포함한 이진 검색 알고리즘이 깔끔하게 모듈 형태로 구현되어 있음
• 이 모듈을 이용하면 이진 검색을 파이썬다운 방식으로 다음과 같이 좀 더 간단히 풀이 가능

[bisect 모듈]
출처: Lib/bisect.py
(기능 크게 2개로 나뉨)
1) 주어진 list와 target이 있을 때, target이 위치해야 할 인덱스를 구하는 함수

• 문제에 적용)리스트에서 9의 위치는 어디니? = 리스트에서 9가 들어갈 자리는 어디니?
• bisect.bisect_left(a, x, lo=0, hi=len(list)),bisect.bisect_right(a, x, lo=0, hi=len(list))

2) 같은 조건에서 값 target을 올바른 위치에 삽입하는 함수

• bisect.insort_left(a, x, lo=0, hi=len(a))
  

1)
bisect.bisect_left(a, x, lo=0, hi=len(list))

• 오름차 순으로 정렬된 순서를 유지하도록 list에 target을 삽입할 위치를 찾음
• a: list(num)
• x: target
• 매개 변수 lo 와 hi는 고려해야 할 리스트의 부분집합을 지정하는 데 사용
  • lo=: list 범위중 시작 위치
  • hi=: list 범위중 끝 위치
  • 기본적으로 전체 리스트가 사용
• target이 list에 이미 있으면(같은게 있으면), 삽입 위치는 기존 항목 앞(왼쪽).
• 실제로 삽입하진 않음 자리만 찾아줄 뿐임

import bisect as bi
list = [-1,0,3,5,9,12]
target = 9  
bi.bisect_left(list, target)
# 4
print(list)
# [-1,0,3,5,9,12]  # 그대로다(실제로 삽입되지 않았다)

bisect.bisect_right(list, target, lo=0, hi=len(list))
bisect = bisect_right

• 위와 같음
• 차이점) target이 list에 이미 있으면(같은게 있으면), 삽입 위치는 기존 항목 앞(왼쪽).
• 실제로 삽입하진 않음 자리만 찾아줄 뿐임

list = [-1,0,3,5,9,12]
target= 9
bisect.bisect_right(list, target)
# 5
print(list)
# [-1,0,3,5,9,12]  # 그대로다(실제로 삽입되지 않았다)


# 이번엔 list의 범위를 한정해서 출력[problem]
bisect.bisect_left(list, target, lo=1, hi=3)
# list[1]<= in_list < list[3]
# in_list = [0,3]
# 출력 
# 2

[problem]
그런데 위와 같이 아이에 타겟이 리스트에 없는 경우에 -1이 아닌 기존 인덱스 보다 큰 값이 출력 된다.
그러므로 이를 이 문제 맞춰 바꾸면 밑의 코드를 추가해야 한다.

if index < len(nums) and nums[index] == target:
 return index 
else:
 return -1

2)
같은 조건에서 값 target을 올바른 위치에 삽입하는 함수
bisect.insort_left(a, x, lo=0, hi=len(a))

• a에 x를 정렬된 순서로 삽입.

import bisect as bi
list = [-1,0,3,5,9,12]
target = 9  
bi.insort(list, target)
#      # 출력값없다
print(list)
# [-1,0,3,5,9,9,12]  # 9가 해당 위치에 삽입되었다(실제로 삽입되었다)

즉, 이를 이용한 문제 풀이

def search(self, nums: List[int], target: int) -> int:
 index = bisect.bisect_left(nums, target)
  if index < len(nums) and nums[index] == target:
   return index 
  else:
   return -1

구현(자바)

public class bs {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
        binarySearch(arr,2);
    }
 
    public static void binarySearch(int arr[],int value) {
        int mid;
        int left = 0;
        int right = arr.length - 1;
 
        while (right >= left) {
            mid = (right + left) / 2;// 밑의 오류에 의해 이렇게 고치는 게 좋음 middle = left+(right-left)//2
 
            if (value == arr[mid]) {
                System.out.println(value+ "-> index is : " + mid );
                break;
            }
 
            if (value < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
 
        }
    }


}

이진 검색 알고리즘 버그(자바)

사실 이진 검색 알고리즘에는 오랫동안 아무도 발견하지 못한 버그가 있었음.

이 오류는 무엇이었을까?
앞서 65번 문제의 풀이에서, 중앙의 위치를 구하는 풀이 #1 코드의 4행과 풀이 #2 코드의 4행의 코드
[오버플로가 발생하는 중앙의 위치계산]
mid = (left + right) // 2

• left와 right를 더하고 결과를 반으로 나눠 가운데를 계산.
• 수학적으로 잘못된 점은 전혀 없다.
• 그러나 컴퓨터과학에서는 문제를 일으킬 만한 소지가 있는 코드임
  
• 두 수를 더하면 항상 각각의 수보다 큰 수가 된다.
• 그러나 자료형에는 최댓값이 있다.(즉 이 left+right를 담기엔 너무 작은 경우가 있다는 것)
  • left + right가 자료형의 최댓값을 넘어선다면: C에서는 예상치 못한 결과가 나오게 되고, 자바에서는 오류가 발생
  • 좀 더 구체적으로 int 형일 때 \(2^{31}-1\)을 넘어서면 오류 발생
  • 결과가 int 자료형이 허용하는 최댓값을 초과하므로 오버플로(Overflow)가 발생

[개선]
left + (right - left)// 2를 계산하면 오버플로를 피하면서 정확한 mid 값을 구할 수 있음.

• 두 수를 더하고 그 합을 반으로 나누는 대신, 두 수의 뺄셈을 해서 그 차를 반으로 나눈 후 낮은 수에 더한다.
• 그럼 빨간색부분이 안생김
• (right - left)는 항상 right보다 작은 값이 나오므로 오버플로의 위험이 없다.
  • (right - left)// 2에 left를 더한 값은 right를 넘지 않으므로 당연히 오버플로의 위험이 없다.

사실 파이썬은 임의 정밀도 정수형을 지원하기 때문에, 이 문제에서 자유로우며 해당 사항이 없다.

• 그러나 이는 자료형이 엄격한 언어들에는 여전히 발생할 수 있는 문제이기 때문에 주의가 필요
• 반드시 숙지할 필요

65번 문제 풀이 #1의 4행을 수정한 전체 코드

def search(self, nums: List[int], target: int) -> int:
 def binary_search(left, right):
  if left <= right:
    # 자료형을 초과하지 않는 중앙 위치 계산 
    mid = left + (right - left) // 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)