[알고리즘] 이분 탐색

📌개요

정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다.

이분 탐색의 시간 복잡도는 O(logN) 으로 배열을 전수 조사하는 O(N)에 비하면 상대적으로 빠른 탐색 알고리즘에 속한다. 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다.
변수 3개(start, end, mid) 를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이분 탐색의 과정이다.

출처 : https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

🔎사용 조건

배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.

🙅‍♂️분할정복과의 차이

• 분할 정복 알고리즘

  • Divde : 문제를 하나 또는 둘 이상으로 나눈다.
  • Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.

• 이분 탐색

  • Divide : 리스트를 두 개의 서브 리스트로 나눈다.
  • Conquer
    • 검색할 숫자(search) > 중간값이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
    • 검색할 숫자(search) < 중간값이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

🔑코드

1. 반복

public static int binarySearch(int[] array, int target){
	
    int start = 0;
    int end = array.length-1;
    int mid = (end+start)/2;
    
    while(end>=start){
    	if(array[mid] == target){
        	//탐색 완료
        	return mid;
        }
        else if(array[mid] <= target){
        	//값이 오른쪽에 있음
        	start = mid + 1;
        }
        else{
        	//값이 왼쪽에 있음
        	end = mid - 1;
        }
        mid = (end + start)/2;
    }
    //값 없음
    return -1;
}

2. 재귀

int binarySearch1(int key, int low, int high) {
	int mid;

	if(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) { 
        	// 탐색 완료 
			return mid;
		} else if(key < arr[mid]) {
			// 값이 왼쪽에 있음
			return binarySearch1(key ,low, mid-1);  
		} else {
			// 값이 오른쪽에 있음
			return binarySearch1(key, mid+1, high); 
		}
	}
	// 값 없음
	return -1; 
}