[알고리즘] 이진 탐색(Binary Search) 알고리즘

1. 이진 탐색(Binary Search)의 정의

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  • 시작점, 중앙점, 끝점을 이용하여 탐색 범위를 설정한다.
• 이진 탐색을 사용하기 위해서는 리스트가 정렬되어 있어야 한다.

---

2. 이진 탐색 동작 예시

• 찾고자 하는 값이 중간점보다 작다면 중간점 이후는 확인할 필요 X

• 끝점을 기존 중간점의 바로 왼쪽으로 옮기고, 중간점을 재설정
• 찾고자하는 값이 중간점보다 크다면 중간점 이전은 확인할 필요 X

• 시작점을 중간점의 바로 오른쪽으로 옮기고, 중간점을 재설정
• 재설정한 중간점이 찾고자 하는 값이라면 탐색 종료

---

3. 이진 탐색의 시간 복잡도

• 단계마다 탐색 범위를 2로 나누는 것이므로 연산 횟수는 logN에 비례
  • 따라서 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장
    ex. 전체 데이터 개수가 8개일 때, 최악의 경우를 따지면
    • 이진 탐색 1단계 거치고 나면 4개의 데이터 남음
    • 2단계 거치고 나면 2개의 데이터 남음.
    • 3단계 거치고 나면 찾고자 하는 1개의 데이터 남음.
    • N = 8이므로 log8 = 3

---

4. 이진 탐색 구현 코드

🖥️ 반복문

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>& arr, int target, int start, int end)	// 기존 벡터를 복사하지 않고 포인터로 참조하여 시간 복잡도 감소시킴
{
	while (end >= start)
	{
		// 시작점과 끝점의 가운데를 중간점으로 설정
        // mid = (start + end) / 2로 하면 안 됨. 
        // 오버플로우 발생 가능성 & start + end가 음수일 경우 결과가 달라짐.
		int mid = start + (end - start) / 2;
		
		// 설정된 중간점이 찾고자 하는 값이라면 해당 지점 반환 
		if (target == arr[mid]) return mid;		
		// 찾고자 하는 값이 중간점보다 작다면 끝점을 중간점의 왼쪽으로 옮김.
		else if (target < arr[mid]) end = mid - 1;
		// 찾고자 하는 값이 중간점보다 크다면 시작점을 중간점의 오른쪽으로 옮김.
		else start = mid + 1;
	}
	return -1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();
	
	int n, target;
	vector<int> arr;

	cin >> n >> target;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		arr.push_back(x);
	}

	int result = binarySearch(arr, target, 0, n - 1);
	if (result == -1)
		cout << "원소가 존재하지 않습니다." << '\n';
	else
		cout << "Index : " << result << '\n';
	
	return 0;
}

🖥️ 재귀 함수

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>& arr, int target, int start, int end)
{
	if (start > end) return -1;

	int mid = start + (end - start) / 2;
	
	if (target == arr[mid])
		return mid;
	else
	{
		if (target < arr[mid])
			return binarySearch(arr, target, start, mid - 1);	// 그냥 실행시키는 것이 아니고 return 해줘야 함.
		else
			return binarySearch(arr, target, mid + 1, end);
	}
}

// main()은 위와 동일

---

5. lower bound와 upper bound

1. lower bound

: 찾고자 하는 값 이상이 처음 나타나는 위치를 찾는 방법

int lowerBound(int arr[], int start, int end, int target)
{
	int mid;

	while (end > start)	// end가 start보다 작거나 같게되면 멈춤 
	{
		mid = start + (end - start) / 2;

		if (target <= arr[mid])	// 중간점이 찾고자 하는 값보다 크거나 같으면 end = 중간점의 값으로
			end = mid;
		else if (target > arr[mid])	// 중간점이 찾고자 하는 값보다 작으면 start = 중간점 + 1
			start = mid + 1;
	}
    
    if(arr[end] < target)  // arr의 모든 값이 target보다 작다면 (target 이상 값 X) -1 반환
    	return -1;
	return end;
}

2. upper bound

: 찾고자 하는 값을 초과 하는 값이 처음으로 나타나는 위치를 찾는 방법

int upperBound(int arr[], int start, int end, int target)
{
	int mid;

	while (end > start)	
	{
		mid = start + (end - start) / 2;

		if (target < arr[mid])	// 중간점이 찾고자 하는 값보다 크면 end = 중간점의 값으로
			end = mid;
		else if(target >= arr[mid])	// 중간점이 찾고자 하는 값보다 작거나 같으면 start = 중간점 + 1
			start = mid + 1;
	}
    
    if (arr[end] <= target)	 // arr의 모든 값이 target보다 작거나 같다면 (target 초과 값 X) -1 반환	
		return -1;
	return end;
}

3. C++의 라이브러리 함수

1. lower_bound(arr, arr+n, key)

: arr 안에서 key 이상의 값이 처음으로 등장하는 위치를 반환

vector<int> arr = {1, 2, 3, 4, 5, 6, 7}
cout << lower_bound(arr.begin(), arr.end(), 6) - arr.begin();

// 출력 결과 : 5 (6의 인덱스)

2. upper_bound(arr, arr+n, key)

: arr 안에서 key를 초과하는 값이 처음으로 등장하는 위치를 반환

vector<int> arr = {1, 2, 3, 4, 5, 6, 7}
cout << lower_bound(arr.begin(), arr.end(), 3) - arr.begin();

// 출력 결과 : 3 (4의 인덱스)

두 함수의 반환값은 모두 iterator이기 때문에 인덱스 값을 얻고 싶으면 함수의 결과값에서 해당 배열의 시작 iterator인 arr.begin()을 빼줘야 한다.

---

👁️‍🗨️ 참조
유튜브 동빈나(https://youtu.be/94RC-DsGMLo)
https://jackpot53.tistory.com/33
https://chanhuiseok.github.io/posts/algo-55/