binary search(이진 탐색)

프로그램 명: bsearch

제한시간: 1 초

정렬된 수열을 입력으로 받아 이 수열내에 찾고자 하는 수가 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

입력의 첫 수는 검색 대상이 되는 수의 개수 n ( 1 <= n <= 500,000 ) 이고 , 다음 n 개의 수 와 검색대상 수가 입력으로 주어진다. 주어지는 수열의 수와 검색되상의 수는 정수 범위를 넘지 않고 , 입력되는 첫 수가 첫번째 수이다.

출력

찾으면 몇 번째 있는 수인지를 출력하고 찾고자 하는 데이터가 없으면 "not found" 를 출력한다.

입출력 예

입력

5
2 4 6 8 10
4

출력

2

입력

5
2 4 6 8 10
5

출력

not found

출처 | dovelet

정렬된 데이터라고 가정할 때 logN번으로 가장 효과적으로 특정한 데이터를 찾아내는 알고리즘 기법을 binary search(이진탐색)이라고 합니다. 사실은 이 기법은 업다운게임(?)을 생각해보면 쉽게 이해하실 수 있습니다. 업다운게임도 결국에는 연속된 수들을 기준으로 외치는 숫자보다 크면 업! 작으면 다운!을 외치면서 값을 찾아내기 때문이죠.

소스코드를 보시면 쉽게 이해가능 합니다.

---

/*

made by hahahia

binary.cpp

*/

 

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

 

int data[500001];

int main(){   

 

        int n, left, right, center, num;

        cin >> n;

        center = n/2;

        for(int i=0; i<n; i++) // input data

               cin >> data[i];

        cin >> num; // search number

        left = 0;

        right = n-1;

        while(1)

        {

               center = (left + right)/2;

               if(data[center] < num)

                       left = center + 1;

               else if(data[center] > num)

                       right = center - 1;

               else if(data[center] == num)

               {

                       cout << center+1 << endl; // found number. and program exit

                       return 0;

               }

               if(left > right) break;

        }

        cout << "not found" << endl; // not found

        return 0;

}