[Algorithm-PS] 이분 탐색

 

이분 탐색이란, 정렬되어 있는 배열에서 탐색 범위를 절반씩 줄여나가며 데이터를 탐색하는 방법이다.

보통 시작점 start, 중간점 mid, 마지막점 end 변수를 이용하여 탐색한다.

 

start가 end와 동일하거나 커지기 전까지(>= or >)(알고리즘에 따라 둘 중 하나가 선택됨) 반복하며 탐색 범위를 줄여나간다.

...

int[] arr = ...

int start = 0;
int end = arr.length - 1;

int findNumber = 10;

int mid = 0;

while(start <= end) {
	
    // 또는 mid = start + ((end - start) / 2); 도 가능함
    // 입력값의 범위에 따라 오버플로우 발생 여부가이 있는 경우 사용한다.
    mid = (start + end) / 2;
    
    // mid에 있는 값이 찾는 수 보다 큰 경우
	if (arr[mid] > findNumber) {
    	end = mid - 1;
    }
    // mid에 있는 값이 찾는 수 보다 작거나 같은 경우
    else {
    	start = mid + 1;
    }
}

// mid에 우리가 찾는 숫자가 있음

 

위 코드처럼 이분 탐색을 구현할 수 있다.