[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)

이분 탐색 이란?

• 이분 탐색 / 이진 탐색 알고리즘은 "오름차순으로 정렬된 리스트"에서 특정한 값의 위치를 찾는 알고리즘이다. 
• 처음부터 끝까지 순서대로 탐색 하는 것보다 빠르게 탐색할 수 있다!

 

탐색 방법

1. 리스트를 정렬한다. 
2. start = 0, end = n으로 설정한다. 
3. mid = ( start + end ) // 2
4. 구하는 숫자와 mid 를 비교한다. 
5. 구하는 숫자보다 mid가 크다면 start = mid +1, mid보다 작다면 end = mid - 1
6. start < end가 될 때까지 3 ~ 5의 순서를 반복하며 숫자를 탐색

 

아래의 그림은 0 ~ 100 사이에서 78을 탐색하는 과정이다. 

 

이분 탐색 코드 (Python)

def binary_search(array, target):
	start = 0
    end = len(array) - 1
    
    while start <= end:
    	mid = (start + end) // 2
        
        if array[mid] == target:
        	return True
        elif array[mid] > target:
        	end = mid - 1
        else:
        	start = mid + 1
    return False

sample_array = [1, 4, 5, 2, 6, 9, 3, 5]
target = 3
sample_array.sort()

result = binary_search(sample_array, target)

print("{} in array".format(target) if result else "{} not in array".foramt(target))

## 3 in array