이분 탐색1 [Python] 이분/이진 탐색 이분/이진 탐색이란? 이분 또는 이진 탐색이라 불리는 이 탐색은(이하 이분 탐색) 탐색 범위를 반씩 좁혀가는 탐색하는 알고리즘이다. 이분 탐색은 결정 문제의 답이 이분적일 때, 그리고 데이터가 정렬되어 있을 때 사용할 수 있다. 보통 정렬되지 않은 리스트를 탐색해야 할 때 앞에서부터 순차적으로 확인하는 탐색인 순차 탐색을 쓰지만, 원소를 하나씩 확인해야 하기에 시간 복잡도가 O(n)이다. 그러나 이분 탐색은 계속해서 탐색 범위를 반으로 줄여나가기에 O(logN)으로 순차 탐색보다 빠르다. 구현 이분 탐색을 구현하는 방법에는 2가지가 있다. 하나는 재귀 함수, 그리고 다른 하나는 반복문을 사용하는 것이다. 재귀 함수로 구현 def binary_search(array, target, start, end): .. 2022. 3. 2. 이전 1 다음