[자료구조] 이분 탐색/이진 탐색 (Binary Search)

이분 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 반씩 좁혀가며 데이터를 탐색하는 방법이다.

또한, 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

변수 3개 (start, mid, end)를 사용해 탐색하며, 찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교해 원하는 데이터를 찾는다.

단순한 배열 순회(O(N))보다 시간복잡도에서 이점을 가진다.

 

입출력 예시

let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
console.log(output);

 

function binarySearch(arr, target){
	let [start, end] = [1, Math.max(...arr)];
     
    while(start <= end){ // 점점 배열을 축소시키며 start와 end 순서가 어긋날 때 종료
    	let mid = Math.floor((start + end) / 2);
        
        if(target === arr[mid]){
        	return mid;
        } else if (target < arr[mid]){
        	end = mid - 1;
        } else {
        	start = mid + 1;
        }
    }
    
    return -1 ;   
}

 

1. [start, end]를 지정해준다. 이 때, end는 배열의 가장 큰 값이므로 Math.max를 이용해 찾아준다.

3. mid는 start + end 의 중간이므로 2로 나눠준다.

4. 만약 target인 2 와 배열의 중간값이 같다면 그대로 리턴

5. target이 mid보다 작으면 end 를 mid - 1 로 지정해 중간값의 왼쪽부분을 탐색한다.

6. target이 mid보다 크면 start 를 mid + 1 로 지정해 중간값의 오른쪽부분을 탐색한다.

7. 종료 조건은 중간값이 찾는 값과 같아질 때까지 반복하며,

8. 반복의 범위는 남겨진 배열들이 계속 짧아지며 start 시점이 end 시점보다 커질 때까지 반복한다.

9. 반복문을 나왔을 때 리턴값을 찾지 못하면 배열에 없다는 것과 같으므로 -1 을 리턴한다. 

 

[백준 문제]

1. https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

2. https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

3. https://www.acmicpc.net/problem/2110

2110번: 공유기 설치