C++ Binary Search

특정 숫자 찾기

정렬되어 있는 상태에서 지혜롭게 찾기 위해서 사용하는 방법 Binary Search

1 3 5 6 8 9 10

에서 9를 찾기 위해서는 우선 가운데 값을 9와 비교해 본다. 

가운데 값 6은 9보다 작기 때문에 9는 오른쪽에 존재 한다. 그래서 왼쪽 값들은 버리다. 

8 9 10 또 다시 가운데 값인 9와 비교해 본다. 

결과적으로 9를 찾았다. 

--------------------------------------------------------------------------------------

절반씩 찾아가기 때문에 O(log N) 만큼 걸린다. 하지만 정렬을 해야 하기 때문에 O(N longN) 만큼 걸린다.

결국

- 숫자 별로 없는데 찾는걸 많이 사용하는데 사용하는 알고리즘 

- 이미 정렬되어 있는 경우를 줬을때 

>> Binary search 사용하는데 좋다.

2가지 방법으로 풀이 

1. 재귀를 사용해서 

#include <iostream>

using namespace std;

int binarySearch(int arr[],int start, int end, int value)

{

//arr의 start 부터 end 까지 값들 중에서

//value 가 존재 한다면 그 위치를 반

//환 그렇지 않으면 -1을 반환

if(start > end)

{

return -1;

}else if(start ==end){

if(arr[start] == value )return start;

else return -1;

}else{

int mid = (start+end)/2;

if(arr[mid] == value) return mid;

else if(arr[mid] > value) return binarySearch(arr,start,mid-1,value);

else return binarySearch(arr,mid+1,end,value);

}

}

int main() {

int num;

int arr[100];

cin >>num;

for(int i=0;i<num;i++)

{

cin>>arr[i];

}

int insert;

cin >>insert;

int inx = binarySearch(arr,0,num-1,insert);

if(inx == -1)

{

cout<< "없습니다."<<endl;

}else{

cout<< inx+1 <<"에 위치 합니다."<<endl;

}

}

2. 재귀로 말고 풀기 반복문으로 풀기 

#include <iostream>

using namespace std;

int binarySearch(int arr[],int myStart,int myEnd,int value)

{

//arr 의 mystart 부터 myend까지 중에서

// value 를 찾아 그 위치를 반환

//없으면 -1 반환

int start;

int end,mid;

if(arr[myStart] > value) return -1;

else if(arr[myStart] == value) return myStart;

if(arr[myEnd] < value) return -1;

else if(arr[myEnd] == value) return myEnd;

start = myStart;

end = myEnd;

while(start+1 < end){ //두 값이 붙어 있지 않을때 까지

mid=(start+end)/2;

if(arr[mid] == value) return mid;

else if(arr[mid] > value) end = mid;

else start = mid;

}

return -1;

}

int main() {

int n,m;

int arry[100000];

int value;

cin >>n >>m;

for(int i =0;i<n;i++)

{

cin>>arry[i];

}

for(int i =0;i<m;i++)

{

cin >> value;

int inx = binarySearch(arry,0,n-1,value);

if(inx == -1)

{

cout<<"NO"<<endl;

}else{

cout<<"YES"<<endl;

}

}

return 0;

}