이분탐색(Binary Search)

이분 탐색

    - 정렬된 배열에서 중간에 위치한 값과 목표 값을 비교해서 목표 값의 위치를 찾는 알고리즘

    - 목표 값이 있는 지 확인하는 알고리즘

 

 

 

동작

    1. 배열의 맨 왼쪽과 맨 오른쪽을 가리킬 index 변수 두 개 left와 right를 선언합니다.

    2. left와 right의 중간 위치인 mid를 구하고 mid 위치에 있는 값과 목표 값을 비교합니다.

        2-1. 목표 값과 mid에 위치한 값이 같으면, 탐색을 멈춥니다.

        2-2. 목표 값보다 mid에 위치한 값이 작으면, left = mid + 1 해줍니다.

        2-3. 목표 값보다 mid에 위치한 값이 크면, right = mid + 1 해줍니다.

     3. 탐색이 끝날 때까지 2번을 반복합니다.

 

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

 

 

구현

#include <stdio.h>
#include <iostream>
 
using namespace std;
 
int main(void){
 
    int target;
     int answer;
 
    int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 15 };
 
    cin >> target;
    int left = 0, right =  9;
 
    while (left <= right){
 
        int mid = (left + right) / 2;
        if (arr[mid] > target)
            right = mid - 1;
        else if (arr[mid] < target)
            left = mid + 1;
        else
        {
            answer = mid;
            break;
        }
    }
 
    cout << answer << endl;
 
    return 0;
}
 

 

 

 

상한선과 하한선

    - 목표 값을 찾는 문제가 아니라면 상한선(upper bound)과 하한선(lower bound) 알고리즘을 자주 사용합니다.

    - 상한선(upper bound) : 목표 값보다 큰 값이 처음 나오는 위치 반환(초과)

    - 하한선(lower bound) : 목표 값보다 크거나 같은 값이 처음 나오는 위치 반환(이상)

 

 

 

구현

int lower_bound(vector<int> v, int target){
    int left = 0;
    int right = v.size()-1;
    int mid;
    
    while(left < right){
    
        mid = (left + right) / 2;
        
        if(target <= v[mid]) right = mid;
        else if(target > v[mid]) left = mid + 1;
    
    }
    return left;
}
 
 
 
int upper_bound(vector<int> v, int target){
    int left = 0;
    int right = v.size()-1;
    int mid;
    
    while(left < right){
    
        mid = (left + right) / 2;
        
        if(target < v[mid]) right = mid;
        else if(target >= v[mid]) left = mid + 1;
    
    }
    return left;
}

 

 

 

 

 

 

 

 

 

 

참조

    - 이분탐색