[알고리즘] 이분 탐색

이분 탐색 알고리즘이란? 

정렬되어 있는 리스트에서 탐색 범위를 절반씩 줄여가며 원하는 데이터를 탐색하는 알고리즘이다.

이분 탐색, wiki

정렬된 리스트에서 중간 값을 선택하고 선택한 값과 찾고자 하는 값의 크고 작음을 비교한다. 선택한 중간값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

꼭 정렬해야함을 잊지 말자!

 

이분 탐색 알고리즘 구현 - C++

이분 탐색은 O(log N) 의 시간복잡도를 가진다.

#include<iostream>

using namespace std;

int main(){
    int arr[10]={1,2,3,4,5,6,7,8,9};
    int target=6;
    int low=0, high=9;	//시작 인덱스, 끝 인덱스
	int res=0;
    
    //이분탐색 부분
    while(low <= high){
        int mid = (low + high) / 2;
        if(arr[mid] == target) 
        	res = mid;
        if(arr[mid] > target) 
        	high = mid - 1;
        else 
        	low = mid + 1;
    }
    
    cout<<res;
    
    return 0;
}

 

lower_bound

찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위한 함수

#include <iostream>
#include <algorithm>

using namespace std;

int main() {

	int arr[6] = { 1,2,3,4,5,6 };
	cout << lower_bound(arr, arr + 6, 6) - arr; // 5

	return 0;
}

lower_bound의 반환형은 Iterator 이므로, 인덱스를 구하고 싶다면 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 됩니다.

6이 6번째에 나타나므로 결과는 인덱스 5이다.

 

upper_bound

찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위한 함수

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {

	vector<int> v = { 1,2,3,4,5,6 };
	cout << upper_bound(v.begin(), v.end(), 5) - v.begin(); // 5
    
	return 0;
}

5가 5번째 나타나므로 결과는 인덱스 5이다.