24. 이분검색

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

8 32

23 87 65 12 57 32 99 81

 

출력예제 1 

3

 

풀이 

 

lt		mid		rt
		else if(a[mid]<key)	lt = mid+1
	rt=mid-1	else

 

- 전체 루프는 lt<=rt (범위가 줄어들수록 lt-rt사이 간격이 좁아지며 결국 같이 만남)

- lt와 rt를 기준으로 가운데 값을 mid

- mid 와 key 값이 일치하면 그대로 return

- key값이 mid보다 작으면 rt를 mid-1

- key값이 mid보다 크면 lt를 mid+1

- 이분탐색은 벡터 배열의 처음과 끝을 지정하여 범위를 좁혀가며 탐색, 데이터를 정렬한 후에 탐색함

 

 

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

// 24. 이분탐색
int main() {
    int n = 0, key, i, lt=0, mid, rt ;
    //배열 크기 및 탐색할 값 입력
    scanf("%d %d", &n, &key);
  
    vector<int> a(n);

    // vector 정렬
    for(i=0; i<n; i++){
        scanf("%d", &a[i]);
        //a.push_back()도 가능
    }
    sort(a.begin(), a.end());
    rt=n-1;
    
    while(lt<=rt){
        mid=(lt+rt)/2;
        if(a[mid]==key){
            printf("%d\n", mid+1);
            return 0;
        }
        else if(a[mid]>key) rt=mid-1;
        else lt=mid+1;
    }
    return 0;
}