바이너리서치

Score* BinarySearch(Score ScoreList[], int Size, double Target){ int Left, Right, Mid; Left=0; Right = Size-1; while(Left<=Right){ Mid = (Left+Right)/2; if( Target == ScoreList[Mid].score ) return &(ScoreList[Mid]); else if( Target > ScoreList[Mid].score ) Left = Mid + 1; else Right = Mid - 1; } return NULL; } 일단은 데이터들이 정렬되어있어야 한다

내가 찾고자 하는값을 중앙값과 비교한다. 중앙값보다 크면 탐색범위를 오른쪽 반토막,

중앙값보다 작으면 탐색범위를 왼쪽 반토막으로 줄여나가면서 계속 반복한다, left가 right보다 크면 끝

1번 하면 전체 데이터 범위의 1/2, 2번하면 1/4, 3번하면 1/8.... x번하면 (1/2)^x 이 된다

전체 데이터가 n개이고 x번 서치하면 n(1/2)^x가 되는데, 이게 1이 되면 그때 찾은거니까 x를 구하면

x = logN이라는 훌륭한 성능을 갖게된다( 원래는 log2N인데 O(log2N) 은 O(logN)과 같으니까)

그리고 스탠다드 라이브러리에도 있다 원형은 다음과 같다

void *bsearch(const void *key, const boid *base, size_t num, size_t width, int (__cdecl *compare)(const void *, const void*) ); stl의 알고리즘에 있는 바이너리서치는 값이 있는지 없는지 존재만 판별해주지만,

이건 친절하게 그 값의 주소를 알려준다(근데 왜 리턴이 보이드지 @.@???)