[Algorithm] 이진 탐색 (Binary Search)

 

이진 탐색 알고리즘 (Binary Search)

: 정렬된 배열의  중앙값이, 찾으려는 값과 같은지 확인하고

   다르다면 두 값의 대소 관계에 따라 범위를 중간값의 좌/우측으로 좁혀가는 탐색 알고리즘.

 

• 정렬된 배열에서만 사용 가능
• 오름차순(내림차순)으로 순회하는 선형탐색 알고리즘은 O(N)만큼의 시간이 듦
• 그에 반해 이진 탐색 알고리즘은 시간복잡도가 O(logN)으로 훨씬 줄어듦.

 

 

메인 로직

1. 주어진 배열의 양 끝값을 low, high로 설정한 후 중앙값의 인덱스(j)을 찾는다.
2. target이 배열의 중앙값보다 작다면 high = j-1로,
   target이 배열의 중앙값보다 크다면 low = j+1로 재설정하여 범위를 변경한다.
3. target과 중앙값이 일치할 때까지 2.의 과정을 반복한다.
4. low가 high 이상의 값을 가질때까지 안 나왔다면, target은 배열에 없으므로, 반복을 끝낸다.

 

 

다음의 그림을 예시로, 배열을 순회하며 target 37을 탐색한다고 하자.

첫 범위는 배열의 전체이므로 중앙값인 23과 target을 비교한다. 23 < 37이므로 23을 기준으로 오른쪽에 있는 배열 [29, 31, 37, 41, 43, 47, 53, 59]이 새로운 범위가 된다. 이 과정을 반복하면

[29, 31, 37, 41, 43, 47, 53, 59]의 중앙값 41 > 37

=> [29,31,37]의 중앙값 31 > 37

=> [37]

 

단 3번만에 37을 찾을 수 있다. 그에 반해 선형탐색은 11번만에 찾을 수 있는 모습이다.

 

 

 

예시 코드(Python)

def binary_search(num_list, target):
    low = 0 ; high = len(num_list)-1; j = (low+high)//2		# j가 중앙값
    if target<num_list[low] or target>num_list[high]:	# 범위 밖의 target에 대한 예외처리
        return -1
    while(low <= high):
		j = (low+high)//2  
        if num_list[j] == target: 
        	return j
        elif num_list[j]<target:
            low = j+1
        else:
            high = j-1
     return -1

 

 

---

관련 백준 문제 

• 1920 수찾기
• 2805 나무 자르기