[알고리즘] 6. 이진 탐색

Index

1. 순차 탐색

2. 이진 탐색

3. 이진 탐색 라이브러리

4. 파라메트릭 서치

5. 추천 문제

6. 참고자료

---

1.  순차 탐색

순차 탐색(Sequential Search)

- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

 

2.  이진 탐색

이진 탐색(Binary Search)

- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

- O(log N)

 

(재귀적 구현)

def binary_search(arr, target, start, end):
  if start > end:
    return None
  mid = (start + end) // 2
  if arr[mid] == target:
    return mid
  elif arr[mid] > target:
    return binary_search(arr, target, start, mid-1)
  else:
    return binary_search(arr, target, mid+1, end)

(반복문 구현)

def binary_search(arr, target, start, end):
  while start <= end:
    mid = (start + end)//2
    if arr[mid] == target:
      return mid
    elif arr[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  return None

 

3.  이진 탐색 라이브러리

이진 탐색 라이브러리(bisect)

- bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

- bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

from bisect import bisect_left, bisect_right

bisect_left(arr, val)
bisect_right(arr, val)

 

4. 파라메트릭 서치

파라메트릭 서치(Parametric Search)

- 최적화 문제를 결정 문제(Yes/No)로 바꾸어 해결하는 기법

- 이진 탐색을 이용하여 해결 가능

 

5.  추천 문제

이진 탐색

- 나무 자르기(https://www.acmicpc.net/problem/2805)

- 랜선 자르기(https://www.acmicpc.net/problem/1654)

- 공유기 설치(https://www.acmicpc.net/problem/2110)

- K번째 수(https://www.acmicpc.net/problem/1300)

- 입국 심사(https://school.programmers.co.kr/learn/courses/30/lessons/43238)

- 징검 다리(https://school.programmers.co.kr/learn/courses/30/lessons/43236)

---

참고 자료

[Video: 동빈나의 이코테 2021(이진 탐색)] https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5