탐색 : 이진탐색

/*
 * http://sosal.tistory.com/
 * made by so_Sal
 */


이진탐색은 정렬이 되어있는 데이터 배열에 사용할 수 있습니다.
찾기를 원하는 value를 받고, 배열의 정 가운데 값과 비교하여
크면, 가운데와 맨 끝의 중간을 비교, 작으면 가운데와 처음을 비교합니다.
이렇게 반씩 줄여나가면서 데이터를 찾는 과정이 binary search 입니다.

그럼 간단한 함수 예제를 볼까요?

#include<iostream>
#include<cstring>
#include<time.h>
using namespace std;

int BinarySearch( int *arr, int size , int object){
     //arr은 정렬된 데이터의 array, object는 찾고자 하는 수의 값을 뜻합니다.
     int left = 0;
     int right = size -1;  //배열은 0부터 n-1까지의 n개 집합이므로, n-1을 right에 대입
     int mid;

     while( left <= right ){  //left == right 같아질 때 탐색은 끝난것입니다.
        
         mid = (left + right) / 2 ;
        
         if(object > arr[mid])
             left = mid+1;
         else if(object < arr[mid])    // 찾는게 중간값보다 작으면, 왼쪽 반을 향해 이동
             right = mid-1;
         else if(object == arr[mid])   // 찾는게 중간값보다 크면, 오른쪽 반을 향해 이동
             return mid;
     }
     return -1;
}

int main(){
    srand(time(0));
    int a[30000];
    int j=0;
    for(int i=0;i<30000;i++,j+=2)
        a[i] = j;      //3만개의 정렬된 배열 생성
   
    int result = BinarySearch(a,30000,59892);  //탐색

    printf("result is : %d\n",result);
    for(int i=0;i<30000;i++){
        if(i==result)
            printf("a[%02d] : %02d <-- this is what you want\n",i,a[i]);
        else
            printf("a[%02d] : %02d\n",i,a[i]);
    }
}