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

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

• 이진 검색 (Binary Search)
  • 정렬된 배열에서 타겟을 찾는 검색 알고리즘
  • 시간 복잡도 O(log n)
• 이진 탐색 트리(Binary Search Tree)와의 차이
  • 이진 탐색 트리
    - 정렬된 구조를 저장하고 탐색하는 '자료구조'
  • 이진 검색
    - 정렬된 배열에서 값을 찾아내는 '알고리즘'
• 이진 검색의 구현
  • mid를 구할 때 보통 (left+right) // 2를 사용
  • 그러나 두 수의 합으로 인해 오버플로우가 발생할 수 있음
  • 따라서 다음과 같이 구함
    mid = left + (right - left) // 2