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

1. 이분 탐색

- 정렬된 배열에서 찾고자 하는 수를 찾는 방법

- 계속해서 두가지 경우로 나누면서 탐색

- 인덱스를 이용해 탐색

- 시간복잡도 : O(logN)

 

2. 탐색 방법

1. 배열의 첫번째 인덱스와 마지막 인덱스 번호를 각각 left, right로 저장

2. left와 right의 중간지점인 mid의 인덱스를 (left+right)/2 를 이용해 구함

3. left가 right보다 커지는 시점까지 반복 -> left보다 right가 커지면 찾고자 하는 수가 없는 경우임

4. 배열의 mid번째 값과 내가 찾고자 하는 값을 비교

4-1. 내가 찾고자 하는 값이 mid보다 작은 경우

- 최소한 mid - 1번째 인덱스의 값보다는 작거나 같기 때문에 right를 mid-1로 변경시켜 최대값을 바꿔줌(구간을 바꿔줌)

4-2. 내가 찾고자 하는 값이 mid보다 큰 경우 

- 내가 찾고자 하는 값은 최소 mid + 1보다는 크거나 같기 때문에 left를 mid+1로 변경시켜 최소값을 바꿔줌

4-3. 내가 찾고자 하는 값이 mid와 같은 경우

- 값을 찾은 것이므로 break를 이용해 반복문을 빠져나감

5. 매 반복 시작시 mid의 값을 (left+right)/2로 업데이트 시켜줌

 

3. 소스코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> v = {9,6,3,1,4,2,7,3,0,6,3};
    
    // 이분 탐색은 정렬된 배열의 탐색을 원칙으로 함
    sort(v.begin(), v.end());
    
    int myVal = 7; // 찾고자 하는 값
    
    int LIndex = 0;
    int RIndex = v.size() - 1;
    int MIndex = (LIndex + RIndex) / 2;
    
    while(LIndex <= RIndex)
    {
    	MIndex = (LIndex + RIndex) / 2;
        
        if(v[MIndex] > myVal)
        {
        	// 찾고자 하는 값이 중간값보다 작은 경우 -> 최댓값 갱신            
        	RIndex = MIndex - 1; 
        }
        else if(v[MIndex < myVal)
        {
        	// 찾고자 하는 값이 중간값보다 큰 경우 -> 최솟값 갱신
        	LIndex = MIndex + 1;
        }
        else
        {
        	// 값을 찾은 경우
            break;
        }
    }
    
    cout << v[MIndex] << endl; // 결과 : 7
}