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

개인의 짧은 식견으로 작성했으니, 많은 조언 부탁드립니다.

설명

• 이분탐색은 기본적으로 Array와 같은 자료 구조에서 특정 값을 찾아낼 때 쓰인다.
• 찾고자 하는 값과, 현재 보고 있는 값을 비교하여 왼쪽과 오른쪽으로 탐색 범위를 쪼개 다시 탐색하는 과정을 거친다.
• 보고 있는 값과 찾고자 하는 값의 대소관계가 분명해야 하기 때문에, 이분 탐색을 사용하기 위해서는 배열이 정렬되어 있어야 한다.
• 한번 탐색마다 탐색 범위를 반으로 축소하기 때문에(left or right), O(nlogn)의 TC를 갖는다.

사용처

• 배열 속의 특정 값을 찾고자 할 때.
• 배열의 값들을 활용하여 찾아야 할 값에 특정 범위 내의 최적해를 찾을 때.

Code

• 가장 기본적인 이분탐색 코드는 다음과 같다.

```cpp
#include
#include

using namespace std;

int main(){
//Data - 크기가 5인 배열을 선언.
int arr[] = {1,4,2,6,8};

// 배열이 정렬되어 있어야 이분 탐색을 사용할 수 있으므로 배열 정렬.
sort(arr,arr+5);

// 찾고자 하는 값, 값의 유무를 판단할 boolean 변수 선언
int ans = 2; bool result = false;

//처음 시작할 때 위치는 양 끝 점을 위치로 한다.
int left = 0; right = 5 - 1;

//left index가 right index를 넘어갈 경우, 배열의 모든 범위를 탐색한 것이기 때문에 종료.
while(left <= right){
 //left와 right index의 중간 값을 선언하고, 이 값을 찾고자하는 ans와 비교.
 int mid = (left + right) / 2;

    //1. 찾고자 하는 값보다 중간 값과 같으므로, result 변수값을 변경하고 루프에서 빠져나옴.
    if(mid == ans){
     result = true;
        break;
    }
    //2. 현재 값이 찾고자 하는 값보다 크므로, 현재 값보다 작은 범위에서 다시 탐색을 시작.
    else if(mid > ans) right = mid - 1;
    //3. 2번의 반대 개념이므로 현재 값보다 큰 범위에서 다시 탐색.
    else left = mid + 1;
}

cout << result << endl;

return 0;

}