BinarySearch ( 이진검색 )

Binary Search( 이진검색 )

조건1    : 자료가 오름차순으로 정렬되어 있어야 한다.

조건2    : 자료들의 값은 서로 다른 값이어야한다.

소스코드

#include <stdio.h>

int binary_search ( int arr[] , int start , int end , int target ){

int mid = 0 ;

if ( start > end ){

return -1 ;

} else {

if ( arr [ mid ] = target ) {                        // 목표값을 찾아냄

return mid ;

} else if ( arr [ start ] < target ) {               // 목표값이 해당 자료보다 클 때 ( 우측트리로 이동 )

return binary_tree ( arr , mid + 1 , end , target );

} else if ( arr [ start ] > target ){                 // 목표값이 해당 자료보다 작을 때 ( 좌측트리로 이동 )

return binary_tree ( arr , start , mid - 1 , target );

}

}        // else 끝

}    // binary_tree 종료

int main ( void ) {

int arr[] = { 1 , 3 , 5 , 7 , 9 , 11 , 13 } ;

int result = 0 ;

binary_tree ( arr , 0 , 6 , 3 );

if ( result == -1 ){

puts("찾으시는 값을 존재하지 않습니다.");

}else {

printf("찾으시는 값은 %d번쨰에 위치하고 있습니다." , result + 1 );

}

return 0 ;

} 

ex)    int arr[10] ;

=>    start : 0    /    end : 9

--- 다른 방법 ---

술게임에서 업 다운 게임과 같은 원리

해당 범위의 중간값과의 크기 반복비교

#include<stdio.h>

int cnt = 0;

int BinarySearch( int arr[] , int start , int end , int num ){

while ( start <= end ){

cnt++;

mid = ( start + end ) / 2 ;

if ( arr[mid] > num ){

end = mid - 1;

}else{

start = mid + 1;

}

if ( arr[mid] == num ){

return mid ;

}

return -1;        // arr 배열에서 num을 찾지못한경우

}

}

int main(void){

int arr[10] = { 1,2,3,4,5,6,7,8,9 };

int result = 0;

result = BinarySearch( arr, 0 , 9 ,2 );

return 0;

}