0. 순차 탐색
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
- 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
- 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다.
하지만 시간은 충분하지 않은 경우가 많다. 시간 복잡도: O(N)
1. 이진 탐색: 반으로 쪼개면서 탐색하기
전제: 배열 내부의 데이터가 정렬되어 있다.- 탐색 범위를 절반씩 좁혀가며 탐색
사용 변수:시작점,끝점,중간점- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터 탐색
시간 복잡도: O(logN)(이진 탐색 실행과정 생략)
2. 구현 방법
1. 재귀함수
- 원하는 데이터와 중간 값을 비교
- 원하는 데이터가 중간 값보다 작으면 끝점을
중간 값-1로 함수 재귀 호출 - 원하는 데이터가 중간 값보다 크면 시작점을
중간 값+1로 함수 재귀호출 - 재귀 종료 조건은
시작점> 끝점
소스 코드
#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) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
else return binarySearch(arr, target, mid + 1, end);
}
int n, target;
vector<int> arr;
int main(void) {
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 << result + 1 << '\n';
}
}2. 반복문
- 재귀함수와 유사하다.
- 함수를 재귀 호출하는 대신 시작점 또는 끝점을 재설정하고 반복문을 반복한다.
- 반복문 종료 조건은
시작점>끝점(재귀 함수 종료 조건과 동일)
소스코드
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) end = mid - 1;
else start = mid + 1;
}
return -1;
}
int n, target;
vector<int> arr;
int main(void) {
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 << result + 1 << '\n';
}
}