[Algorithm] Binary Search

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

설명

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

사용처

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

Code

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

#include <iostream>
#include <algorithm>

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;
}

관련 문제 코드

백준 1920번 문제 - 수 찾기
백준 2110번 문제 - 공유기 설치
백준 2467번 문제 - 용액

출처

문제 출처
백준 온라인 저지