이분 탐색(Binary search)
- 정렬된 리스트(배열)에서 원하는 값의 존재 여부를 찾는 알고리즘.
- 반드시 리스트(배열)을 정렬해서 사용해야 한다는 단점이 있다.
- 탐색할 때마다 검사 범위가 절반으로 줄어듬.
이분 탐색의 진행 단계
1. 검사 범위에서 중간 값을 선택해서 찾고자 하는 값이 같은지 확인한다.
2. 만약 찾고자 하는 값이라면 해당 값을 반환한다.
3. 찾고자 하는 값보다 작다면, 검사 범위를 큰 쪽으로 잡는다.
4. 만약 찾고자 하는 값보다 크면, 검사 범위를 작은 쪽으로 잡는다.
5. 1~4번을 반복하다가 원하는 값을 찾으면 해당 값을 반환한다.
lower_boud, upper_bound
- lower_bound : 이분탐색 방식으로 주어진 배열 주소 사이에서 value보다 크거나 같은 값이 처음 등장하는 주소를 반환
- upper_bound : 이분탐색 방식으로 주어진 배열 주소 사이에서 value보다 초과하는 값의 주소를 반환
- 끝까지 탐색했을 때 해당하는 원소가 없으면 마지막 주소 반환
- 탐색할 배열은 오름차순 정렬이 되어있어야함. -> sort 활용
#include <algorithm>
lower_bound(arr,arr+N,value) // 배열의 주소 arr~arr+N까지 탐색하며 value보다 크거나 같은 첫번째 원소의 주소 리턴
upper_bound(arr,arr+N,value) // 배열의 주소 arr~arr+N까지 탐색하며 value을 초과하는 첫번째 원소의 주소 리턴
sort
- 배열 오름차순 정렬 함수
#include <algorithm>
bool comp(int x, int y)
{
return i>j;
}
sort(arr, arr+N); // 배열의 시작 주소와 배열의 마지막 주소 + 1 을 매개변수로 넣어주면 배열이 오름차순 정렬됨
sort(arr, arr+N, comp); // comp()가 아닌 comp를 입력 / 매개변수 x = 앞의 수, y = 뒤의 수를 넣어 x>y인 경우 동작하여 내림차순으로 정렬됨.
binary_search
- 이분 탐색 함수
- 배열은 오름차순 정렬이 되어있어야함.
#include <algorithm>
binary_search(arr, arr+N, value); // 주어진 배열 주소 arr, arr+N 중에 value가 존재하면 true 반환 아니면 false 반환