이진 탐색

---

• 탐색할 리스트를 둘로 나누어서 해당 데이터가 있을만한 곳을 탐색하는 방법이다.
  • 단, 리스트는 정렬되어 있어야한다.

분할 정복과 이진 탐색

• 분할 정복(Divide and Conquer)
  • Divide: 문제를 하나 또는 둘 이상으로 나눈다.
  • Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.
• 이진 탐색
  • Divide: 리스트를 두 개의 서브 리스트로 나눈다.
  • Conquer
    • 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
    • 검색할 숫자 (search) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

시간 복잡도

• 시간 복잡도는 $O(logn)$이다.

이진 탐색 구현

---

def binarySearch(data_list, search_data):
    if len(data_list) == 1 and search_data == data_list[0]:
        return True
    elif len(data_list) == 1 and search_data != data_list[0]:
        return False
    elif len(data_list) == 0:
        return False
    
    medium = len(data_list) // 2
    
    if data_list[medium] == search_data:
        return True
    elif data_list[medium] > search_data:
        return binarySearch(data_list[:medium], search_data)
    else:
        return binarySearch(data_list[medium:], search_data)