[알고리즘 | 자료구조] 이분 탐색(Binary Search)

이분 탐색(Binary Search)

정렬되어 있는 배열에서 데이터를 찾으려 시도할 때,

순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 차는 것이 아니라 탐색범위를 절반씩 줄여가며 찾는 방법이다.

 

예시) 1 2 3 4 5 6 라는 값에서 6을 찾고자 한다.

배열의 중간에 위치한 3이라는 값과 6을 비교한다.

6은 3보다 크므로, 이제 3의 왼쪽에 위치하는 값들은 탐색할 필요가 없으므로 3의 오른쪽에 있는 값들을 대상으로 탐색을 다시 시도한다.

이제 456 남았으므로 다시 중간값인 5와 찾고자하는 대상인 6을 비교한다.

6은 5보다 크므로, 5의 오른쪽에 있는 값들을 대상으로만 탐색을 다시 시도한다.

이제 6만이 남아았는데 6과 6을 비교하면, 값이 일치하므로 탐색을 종료한다.

 

자바 코드

 public static int binarySearch(int[] array, int target){

	int start= 0;
	int end= array.length-1;
	int mid= (end+start)/2;

	while(end-start>= 0){
		if(array[mid]== target){
			//Case: Find target in array
 			return mid;
		}else if(array[mid]<= target){
 			//Case: target is exist in right of array[mid]
			start= mid+1;
		}else{
			//Case: target is exist in left of array[mid]
 			end= mid-1;
 		}
 		mid= (end+start)/2;
 	}
 	//Case: Can't find data in array
 	return -1;
}

파이썬 코드

def binarySearch(array, target):
    start = 0
    end = len(array) - 1
    mid = (end+start)//2

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