<aside> ❓

정렬된 배열 또는 리스트에 적합한 고속 탐색 방법 (시간복잡도 : O(log n)

• 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는 지를 알아내어 탐색의 범위를 반으로 줄인다.

• 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있다.

• 이러한 방법을 반복적으로 사용해 탐색하는 방법 = 이진탐색 or 이분탐색

• 주로 고정된 데이터에 대한 탐색에 적합

  ※ 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않다.

</aside>

☆ 완전탐색으로는 시간제약을 맞추지 못하는 문제의 경우 이분탐색으로 직접 답을 찾아갈 수 있다.

이분탐색의 구현

1. 탐색의 대상이 되는 자료들이 array[low]에서 부터 array[high]에 들어있다고 가정하자. (정렬 상태)

2. low와 high값에 의거해 중간값 mid 값은 (low + high)/2이다.

   ∴ array[low] ~ array[high] = array[low] ~ array[mid-1] + array[mid+1] ~ array[high]

3. array[mid] 값과 구하고자 하는 key 값을 비교한다.

   1. key > mid : 구하고자 하는 값이 중간값보다 높다면 low를 mid+1로 만들어 줌
   2. key < mid : 구하고자 하는 값이 중간값보다 낮다면 high를 mid-1로 만들어 줌
   3. key == mid : 구하고자 하는 값을 찾음 → 중간값을 리턴

4. low > high (모순관계)가 될 때까지 반복하면서 구하고자 하는 값을 찾는다.

   → 모순관계 도달 시, 탐색 실패로 -1 또는 false 반환

재귀적 탐색

public 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); // left array
		else return binarySearch1(key, mid+1, high); // right array
	}
	
	return -1; // 탐색실패
}

반복적 탐색

public int binarySearch2(int key, int low, int high) {
	int mid;
	
	while(low <= high) {
		mid = (low + high) / 2;
		
		if(key == arr[mid]) return mid; // 탐색 성공
		else if(key < arr[mid]) high = mid - 1;
		else low = mid + 1;
	}
	
	return -1; // 탐색실패
}

⭐Binary Search in Programmers

프로그래머스에 있는 이분탐색 문제들

입국심사

징검다리