[알고리즘][C++] 이분탐색

input

23

87

65

12

57

32

99

81

 

 

정렬된 배열 상태

+ 두 개의 변수 필요 (left, right)

 

 

🔽lt                                         📍mid                                                          🔽rt

12

23

32

57

65

81

87

99

 

mid = (lt + rt) /2;
    = 0+7 / 2 
    = 3

 

 

a [mid]  값과 32(key) 비교 !! 

 

if ( a[mid] == key ) "mid+1" 출력 

else if ( a[mid] > key ) // mid 보다 큰 인덱스에는 해당 값이 없음 (=4~7에는 없음) 
	rt = mid-1;

else if ( a[mid] < key ) //mid 보다 작은 인덱스에는 해당 값이 없음 (=0~2범위에는 없음) 
	lt = mid+1;

 

=>  a[mid] > key

 

 

🔽lt          📍mid       🔽rt                                                                     

12

23

32

57

65

81

87

99

=>  a[mid] < key

 

                               🔽lt 🔽rt                                                                   

12

23

32

57

65

81

87

99

                                📍mid 

 

 

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){ 
	freopen("input.txt", "rt", stdin);
	int n, i, key, lt=0, rt, mid, tmp; 
	
	scanf("%d %d", &n, &key);
	vector<int> a(n);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
//		scanf("%d", &tmp); //vector 배열에 삽입하는 방법
//		a.push_back(tmp);
	}
	
//	printf("%d\n", *(a.end()-1)); //81출력됨
	sort(a.begin(), a.end()); //a,end()는 배열의 마지막 자리+1 가르킴
	
	rt=n-1;
	while(lt<=rt){ //lt가 rt보다 커지게 되면 key 값은 배열에 없는 것
		mid = (lt+rt)/2;
		if(a[mid]==key) {
			printf("%d", mid+1);
			return 0;
		}
		else if (a[mid]>key) rt=mid-1;
		else if (a[mid]<key) lt=mid+1;
	}
	
	
	return 0;
}