이진(이분) 탐색(Binary search)

<이진 탐색 정의>

 

이진 탐색이란 데이터가 "정렬 되어 있는 배열(오름차순)"에서 특정 값(X)을 찾아내는 알고리즘.

 

<방법>

 

배열에서 임의의 중간값을 선택한 후 이를 X와 비교하여 중간값보다

 

- X가 더 작다면 중간값 기준 왼쪽

- X가 더 크다면 중간값 기준 배열 오른쪽

 

배열에서 다시 임의의 중간값을 선택 후 X와 같은 값을 찾을 때 까지(또는 탐색을 끝까지 했을 경우) 위 과정을 반복하여 탐색한다.

 

 

<코드 구현>

1.반복문 구현

#include <vector>
#include <algorithm>

#define MAX 100
using namespace std;

vector<int> list;


bool BinarySearch(int value) {

	//index값
	int left=0;
    int right=list.size()-1;
    int mid;
    
    while(left<=right) {
    	mid = left+right/2;
        if(list[mid] == value) 
        	return true;
        else if(list[mid] < value) 
        	left = mid+1;
        else 
        	right = mid-1;
    }
    
    return false;
}

int main() {
	int value;
	cin >> value;
	list = vector<int>(MAX,0);
    
    sort(list.begin(), list.end());
    BinarySearch(value);
}

 

2.<algorith> 라이브러리 이용 (binary_search)

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

#define 
using namespace std;

vector<int> list;

int main() {
	int value;	
	list = vector<int>(MAX,0);
	sort(list.begin(), list.end());

	cout << binary_search(list.begin(), list.end(), value) << endl;
    
}