이진 탐색(Binary Search)
✔️ 이진 탐색이란?
이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다.
배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교합니다.
만약 X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들로, X가 중간 값보다 크면 중간 값을 기준으로 우측의 데이터들로
다시 탐색을 시작하여 해당 값을 찾을 때까지 반복합니다.
📌 시간 복잡도
N개의 배열을 이진 탐색하게 되면 N, N/2, N/4, N/8 ... 으로 진행될 것입니다.
여기서 탐색 횟수가 시간 복잡도가 될 것이고 그 값을 K라고 한다면 K = log2N일 것입니다.
즉, 이진 탐색의 시간 복잡도는 O(logN)입니다.
✔️ 이진 탐색의 예시
1. 예를 들어 { 17, 28, 43, 67, 88, 92, 100 } 의 오름차순으로 정렬된 배열에서 43의 값을 찾는 과정입니다.
2. 첫 번째 시도로 가운데의 임의의 값 67을 선택하고 67과 43을 비교합니다.
3. 43 < 67 이므로 43은 가운데 값 67의 좌측에 있다는걸 알 수 있습니다.
4. 두 번째 시도로 67의 좌측 값을인 { 17, 28, 43 } 을 기준으로 다시 탐색합니다.
5. 좌측 배열 들의 가운데 임의의 값인 28을 기준으로 하면 28 < 43 이므로 28의 우측에 있다는걸 알 수 있습니다.
6. 28의 우측 값으로 배열을 다시 설정하면 { 43 } 이 남고 우리가 원하는 값인 43을 찾을 수 있게 됩니다.
✔️ 예시 코드
int binary_search(int arr[], int left, int right, int key) {
int mid = (left + right) / 2;
if(arr[mid] == key) {
return mid;
}
else if(arr[mid] > key) {
return binary_search(arr, left, mid - 1, key);
}
else {
return binary_search(arr, mid + 1, right, key);
}
}이 때 arr는 오름차순으로 정렬된 배열, left는 배열의 첫 번째 인덱스, right는 배열의 마지막 인덱스, key는 우리가 원하는 값입니다.
mid값을 구한 후 우리가 원하는 값과 비교하여 재귀함수를 통해 배열을 재설정하는 방식으로 구현하였습니다.
우리가 원하는 값을 찾을 시 정렬된 배열에서 해당 값의 인덱스를 반환합니다.