[알고리즘] 이분 검색 / 이진 탐색 Binary Search - Javascript 예제

이분 검색 Binary Search

이분 검색은 이진 검색 알고리즘이라고도 한다. 오름차순으로 정렬된 배열에서 특정한 값의 위치를 찾아내는 알고리즘이다. 

처음엔 중간값을 기준으로 중간값이 타겟값보다 큰 경우 중간값 기준 배열의 왼쪽을 탐색하고 그 반대의 경우 중간값 기준 배열의 오른쪽을 탐색한다. 만약 중간값이 타겟값일 경우엔 중간값의 위치가 반환되어진다. 시간 복잡도는 O(log n)이다. 

 

글로 보면 어려우니 밑의 그림과 함께 설명을 보자!

(전체 코드는 맨 밑에 있습니다.)

 

예제: 찾아야할 숫자는 51이고 주어진 배열은 [12, 38, 3, 64, 28, 11, 43, 51] 이다. 

이분 검색 예제

변수 설정

start: 탐색을 할 배열의 시작 위치이다.

end: 탐색을 할 배열의 끝 위치이다.

mid: 탐색 시 기준이 될 중간값의 위치이다. 이 값을 기준으로 start, end 값이 변경된다. 

 

오름차순 정렬

우선 배열을 오름차순으로 정렬한다. 

let start = 0, // 배열의 맨 앞 위치
	end = arr.length - 1; // 배열의 맨 끝 위치
arr = [12, 38, 3, 64, 28, 11, 43, 51];
arr.sort((a, b) => a - b); // 오름차순 정렬

오름차순 정렬 후 배열

초기의 start 값은 0 즉 배열의 맨 앞 위치 , end 값은 배열의 맨 끝 위치 즉, 배열 길이 - 1 이 된다. 

 

중간 위치 설정

배열의 중간 위치 mid를 설정한다. 중간 위치는 start와 end를 2로 나눈 값의 정수값이 된다. 

let mid = parseInt((start + end) / 2);

 

중간 위치 값과 타겟값 비교

중간 위치 값을 기준으로 타겟값이 오른쪽에 있는지 왼쪽에 있는지 확인하는 과정이다. 

만약 중간 위치값보다 타겟값이 클 경우 타겟값이 중간값보다 오른쪽에 위치한 것이기에 탐색 시작 위치 start를 중간값 위치의 바로 다음 위치로 설정된다. 

예제의 mid = 3이므로 arr[mid] 중간값과 target인 51을 비교한다.

중간 위치 값인 28이 51보다 작으므로 중간 위치 기준 오른쪽에 target값이 존재한다는 뜻이다!

즉 mid 3 위치로부터 왼쪽의 배열은 볼 필요가 없다.

시작 위치인 start를 mid+1로 설정한다. ( start = 4 )

start를 mid+1 로 설정한 후

---

2번째 탐색

새로 설정된 start 값을 기준으로 다시 탐색을 시작한다. 중간 위치 값 mid는 5가 된다. 

let mid = parseInt((start + end) / 2); // (4+7)/2 = 5.5 -> parseInt -> 5

 

중간 위치 값과 타겟값 비교 (feat. 2번째 탐색)

위의 첫번째 탐색과 동일하게 중간 위치 값과 타겟값을 비교한다. 중간 위치 값인 43이 타겟값인 51보다 작으므로 시작값은 mid + 1 이 된다.

---

3번째 탐색

배열의 중간 위치를 설정한다. 

let mid = parseInt((start + end) / 2); // (6+7)/2 = 6.5 -> parseInt -> 6

중간 위치 값은 6이 된다. 

 

중간 위치값과 타겟값 비교 (feat. 3번째 탐색)

중간 위치값인 51이 타겟값인 51과 동일하므로 mid 값인 6이 타겟값의 위치가 된다. 즉 답은 6이 된다. 

 while (start <= end) {
	let mid = parseInt((start + end) / 2);
	if (arr[mid] === target) {
    	answer = mid + 1;
        break;
	} else if (arr[mid] < target) {
    	start = mid + 1;
	} else {
    	end = mid - 1;
	}
}

현재까지의 탐색 과정을 코드로 나타낼 경우 위와 같다. 

 

전체 코드

 function search(target, arr) {
	let res; // 결과 값
	let start = 0, // 탐색 시작 위치
    	end = arr.length - 1; // 탐색 끝 위치
    arr.sort((a, b) => a - b); // 오름차순 정렬
    while (start <= end) {
    	let mid = parseInt((start + end) / 2); // 중간값 설정 
		if (arr[mid] === target) { // 중간 위치 값과 타겟값이 동일하면 
        	res = mid; // 중간 위치 값을 결과 값으로 설정
            break; // while 문 종료
		} else if (arr[mid] < target) {
        	start = mid + 1; // 중간 위치 값이 타겟값보다 작은 경우
		} else {
        	end = mid - 1; // 중간 위치 값이 타겟값보다 큰 경우
		}
	}
	return res;
}

let arr = [12, 38, 3, 64, 28, 11, 43, 51]; // 예제 배열
let result = search(51, arr); // 3

 

---

공감과 댓글은 힘이 됩니다 😍

게시글의 잘못 작성된 부분은 댓글로 알려주시면 바로 수정하도록 하겠습니다.