[알고리즘] Binary Search

이분탐색

검색 범위를 줄여가면서 데이터를 검색하는 알고리즘

1. 오름차순으로 정렬된 정수 배열에서 검색 범위를 전 범위로 설정한다.
2. 주어진 값과 검색 범위의 중간값을 비교한다.
   a. 주어진 값 < 중간값 이면 검색 범위를 중간값 ~ 범위 내 최댓값으로 설정
   b. 주어진 값 > 중간값 이면 검색 범위를 범위 내 최솟값 ~ 중간값으로 설정
   c. 주어진 값 == 중간값 이면 중간값 인덱스 반환
3. 주어진 값을 찾을 때까지 2. 를 반복한다.

⚠️ 종료 조건과 범위를 헷갈리는 경우가 잦으니 주의하자.

i. 주어진 값이 배열에 존재하는 경우
ii. 주어진 값이 배열에 존재하지 않는 경우

코드 구현과 시간복잡도

1. 재귀

   int binary_search(vector<int> arr, int val, int start, int end){
   	if(start > mid)   // 값 없음
   		return -1;
   				
   	int mid = (start + end) / 2;
   	if(val == arr[mid])
   		return mid;
   	else if(val < arr[mid])
   		return binary_search(arr, val, start, mid - 1);
   	else
   		return binary_search(arr, val, mid + 1, end);
   }

2. 비재귀 - 반복문

   int binary_search(vector<int> arr, int val){
   	int start = 0, end = arr.size() - 1;
   	while(start <= end){
   		if(val == arr[mid])
   			return mid;
   		else if(val < arr[mid])
   			end = mid - 1;
   		else
   			start = mid + 1;
   	}
   	return -1;
   }

재귀/비재귀 두 경우에 시간복잡도는 동일하다.

만약 같은 조건의 배열이 주어지고 이를 순차 탐색(앞에서부터 차례대로 탐색)한다면 O(N) 의 시간복잡도가 주어진다.

⚠️ 이분탐색은 정렬된 배열에서만 사용할 수 있음을 주의하자.