이분 탐색 알고리즘(Binary Search Algorithm)

Binary Search Algorithm

Binary Search Algorithm

- 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘

- 모든 값을 순회해야 하는 일반적인 Search보다 더 빠르다는 장점이 있음

- 중앙값을 찾는 값에 비교

-> (중앙값) > (찾는 값) : 중앙 값 기준으로 왼쪽(작은 부분)을 탐색

-> (중앙값) < (찾는 값) : 중앙 값 기준으로 오른쪽(큰 부분)을 탐색

Binary Search Process

- left를 0으로 초기화, right를 검색하는 리스트(배열)의 마지막 원소의 인덱스로 초기화

- mid 변수를 (left+right)/2로 설정하며 계속해서 탐색

- left > right가 되는 순간 탐색이 종료되고 그전에 해당 값을 찾으면 종료

Example) 1~8에서 7 찾기

1) left = 배열의 시작 index(0), right = 배열의 마지막 index(7)

2) mid = (left+right)/2의 값을 넣어줌. (0+7)/2 = 3, mid = 3, array[3] = 4

3) (찾는 값) > (mid의 값)이므로 left = mid+1해서 다시 수행

4) mid = (left+right)/2의 값을 넣어줌. (4+7)/2 = 5, mid = 5, array[5] = 6

5) (찾는 값) > (mid의 값)이므로 left = mid+1해서 다시 수행

6) mid = (left+right)/2의 값을 넣어줌. (6+7)/2 = 6, mid = 6, array[6] = 7

찾는 값(7) = array[mid](7)이므로 해당 값을 찾아 이분 탐색이 종료

Binary Search Source Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector <int> sort_arr;
void Binary_Search(int find_num) {
    int left = 0, right = sort_arr.size()-1,mid;    // left와 right 초기화
    int res = -1;
    while (left <= right) {                        // left > right이면 종료
        mid = (left + right) / 2;                    // mid 설정
        if (sort_arr[mid] > find_num) {        // 찾는 값이 현재 값보다 작은 경우
            right = mid - 1;
        }
        else if (sort_arr[mid] < find_num) {    // 찾는 값이 현재 값보다 큰 경우
            left = mid + 1;
        }
        else {
            res = mid;
            break;
        }
    }
    if (res == -1) {
        cout << "find_number " << find_num << " is not found" << endl;
        return;
    }
    cout << "sort_arr[" << res << "] is find_number " << find_num << endl;
    return;
}
 
int main()
{
    int find_num;
    int num;
    while (1) {
        cin >> num;
        if (num == -1) {
            break;
        }
        sort_arr.push_back(num);
    }
    sort(sort_arr.begin(), sort_arr.end());
    cin >> find_num;
    Binary_Search(find_num);
    
}

여러 값들을 입력받은 후 이분탐색을 하는 코드.

양수만 입력받을 수 있게 구현했고, -1이 입력으로 들어오면 값 입력이 끝남

이분 탐색은 정렬된 리스트에서만 할 수 있으므로 <alogrithm>라이브러리의 sort함수 사용

찾을 값을 입력 받고 이분 탐색 실행