이진 검색 알고리즘 최적화

Question

이진 검색에서는 보다 큰 값과 다른 값의 두 값을 비교합니다. 그렇지 않으면 중간 값입니다. 우리가 한 번만 점검 할 필요가 있도록 최적화하는 방법은 무엇입니까?

bool binSearch(int array[], int key, int left, int right) 
{ 

    mid = left + (right-left)/2; 
    if (key < array[mid]) 
     return binSearch(array, key, left, mid-1); 
    else if (key > array[mid]) 
     return binSearch(array, key, mid+1, right); 
    else if (key == array[mid]) 
     return TRUE; // Found 

    return FALSE; // Not Found 
} 

Answer 1

먼저 표준 기능 bsearch()을 사용해 보겠습니다. 자신의 접근 방식보다 더 나은 성과를 거둘 가능성이 있습니다.

Answer 2

이진 검색 알고리즘을 최적화하려면 재귀를 반복으로 대체해야합니다. 위키피디아의 예제를 참조하십시오.

자세한 내용이 필요하면 알려주세요.

Answer 3

정수의 경우 중요하지 않습니다.하지 마십시오.

더 비싼 비교의 경우 <에 -1, 0, 1을 사용하십시오. C 라이브러리 함수 strcmp 또는 Java의 compareTo()와 같습니다.

Answer 4

설명하는 방식으로 시도하고 최적화하는 것은 좋지 않습니다. Binary Search Algorithm article on Wikipedia에서 : 단 하나 개의 비교와 b하지만 거짓되는 시간의 나머지 절반과 두 번째 비교가 될 수 있도록

약 절반의 시간, 첫 번째 테스트는 사실 일 것이다 강요된. 어떤 버전은 두 번째 테스트를하지 않으므로 스팬이 0으로 줄어들 때까지 평등성을 결정하지 못하도록하고 따라서 조기 종결 가능성을 미리 알려주기 때문에 너무 심해서 검색 시간의 절반 정도를 기억하십시오 한도가 한도에 미치지 못하는 일치하는 값에서 발생합니다.

그것은 (예를 들어 3에서와 같이) 명령을 사용하여 여전히 더이 문제를 만들기 위해 매우 쉽습니다 등 오히려 초기 평등을 검출하는 것보다

(가에 나타날 수로)

if a = b then action3 
else if a > b then action2 
    else action1; 

로, 이렇게하면 검색의 마지막 반복을 제외하고 모두에 대해 두 번의 비교가 수행됩니다. 포트란 같은

일부 언어는,이 단계는 세 가지 섹션로 분기합니다 (Three-way comparison example의 열 번째 라인 참조)하는 것이 하나 개의 비교와 함께 할 수있는 세 방향 비교가 있습니다. 귀하의 언어가 3- 웨이 테스트를 지원하지 않는다면 (대부분의 언어는 그렇지 않습니다), 두 가지 비교가 최선책입니다.

은 동일한 기사에서 iterative implementation을 확인하는 것이 좋습니다.

Answer 5

게시 한 코드에서 마지막 비교를 제거 할 수 있습니다. 즉, key이 array[mid]보다 작거나 array[mid]보다 큰 경우 정의에 따르면 동일합니다. 따라서 코드는 다음과 같습니다.

mid = left + (right-left)/2; 
if (key < array[mid]) 
    return binSearch(array, key, left, mid-1); 
else if (key > array[mid]) 
    return binSearch(array, key, mid+1, right); 
else 
    return TRUE; // Found 

또한 마지막 줄을 제거했습니다. 원래 코드에서는 return FALSE;이 실행될 수 없습니다. 나는 당신이 binSearch의 시작 부분에 수표를 가지고 있다고 가정하여, left < = right인지 확인합니다.

C에서는보다 작음,보다 같음, 더 큰 것을 기반으로 삼 방향 비교/분기를 수행 할 방법이 없으므로 세 가지 가능성 중에서 두 가지 비교를 수행해야합니다.

Answer 6

Ganesh M - 키가 배열에 없으면 함수가 끝나지 않는 루프 안에 갇히게됩니다. FALSE를 반환 할 수는 없습니다.

키가없는 경우 삽입 포인터를 찾는 최적의 방법은 무엇입니까?

"캐스케이드 인 경우"<, == 및>에 해당하는 조건부 조건 만 TRUE를 반환하거나 영원히 계속 계산합니다.

키가 존재하지 않는 것으로 확인 된 경우 최적의 조건이 필요합니다.

검색 속도가 느려지는 것을 알고 있지만, 가장 느린 속도로 속도를 줄이려고합니다.

log (N)/log (2)를 사용하는 것은 좋은 생각 인 것 같지만 N이 2의 거듭 제곱이 아닐 때 상황이 달라질 수 있습니다.

아마, 나는 2의 거듭 제곱의 크기를 가진 배열을 선택하고 간단한 while 루프를 사용해야 할까?

중점 == 경계가 비교 횟수를 너무 많이 증가시키지 않는지 확인합니까?

Answer 7

이진 검색 알고리즘의 최적화 단계를 재구성하려고했습니다. 나는이 반복 버전으로 시작 :

int binsearch_2(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    while(size > 0){ 
    size_t w=size/2; 
    if(p[w+1] <= key){ p+=w+1; size-=w+1; } else size =w; 
    } 
    *index=p-array; return p[0]==key; 
} 

루프에서 작은 크기를 줄이기 :

int binsearch_1(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    int found=0; 
    while(size > 0){ 
    size_t w=size/2; 
     if(p[w] < key ){ p+=w+1; size-=w+1; } 
    else if(p[w] > key ){   size =w; } 
    else /* p[w] == key */{ p+=w; found=1; break; } 
    } 
    *index=p-array; return found; 
} 

루프에서 비교를 제거 특별한 경우를 이동,

int binsearch_3(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    while(size > 8){ 
    size_t w=size/2; 
    if(p[w+1] <= key){ p+=w+1; size-=w+1; } else size =w; 
    } 
    if(size==8){ if(p[5] <= key){ p+=5; size=3; } else size=4; } 
    if(size==7){ if(p[4] <= key){ p+=4; size=3; } else size=3; } 
    if(size==6){ if(p[4] <= key){ p+=4; size=2; } else size=3; } 
    if(size==5){ if(p[3] <= key){ p+=3; size=2; } else size=2; } 
    if(size==4){ if(p[3] <= key){ p+=3; size=1; } else size=2; } 
    if(size==3){ if(p[2] <= key){ p+=2; size=1; } else size=1; } 
    if(size==2){ if(p[2] <= key){ p+=2; size=0; } else size=1; } 
    if(size==1){ if(p[1] <= key){ p+=1;   }    } 
    *index=p-array; return p[0]==key; 
} 

재 배열 if 문을 [크기 == pow (2, N) -1] 끝까지 :

int binsearch_4(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    while(size > 8){ 
    size_t w=size/2; 
    if(p[w+1] <= key){ p+=w+1; size-=w+1; } else size =w; 
    } 
    if(size==8){ if(p[5] <= key){ p+=5; size=3; } else size=4; } 
    if(size==6){ if(p[4] <= key){ p+=4; size=2; } else size=3; } 
    if(size==5){ if(p[3] <= key){ p+=3; size=2; } else size=2; } 
    if(size==4){ if(p[3] <= key){ p+=3; size=1; } else size=2; } 
    if(size==2){ if(p[2] <= key){ p+=2; size=0; } else size=1; } 

    if(size==7){ if(p[4] <= key){ p+=4; size=3; } else size=3; } 
    if(size==3){ if(p[2] <= key){ p+=2; size=1; } else size=1; } 
    if(size==1){ if(p[1] <= key){ p+=1;   }    } 
    *index=p-array; return p[0]==key; 
} 

변경하는 경우 switch 문에 문 : 코드에서 처리하는 일반적인 경우를 제거

int binsearch_6(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    switch(size){ 
#define C(n) case ((size_t)1<<n)-1: if(p[1<<(n-1)]<=key) p+=1<<(n-1); 
#if SIZE_MAX == UINT64_MAX 
               C(63) C(62) C(61) 
    C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51) 
    C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41) 
    C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32) 
#endif 
                  C(31) 
    C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21) 
    C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11) 
    C(10) C(9) C(8) C(7) C(6) C(5) C(4) C(3) C(2) C(1) 
#undef C 
     break; 
    default: 
     while(size > 0){ 
     size_t w=size/2; 
     if(p[w] < key){ p+=w+1; size-=w+1; } else size=w; 
     } 
    } 
    *index=p-array; return p[0]==key; 
} 

: 특별 모든 경우를 처리하기 위해 switch 문을 확장

int binsearch_5(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    while(size > 8){ 
    size_t w=size/2; 
    if(p[w+1] <= key){ p+=w+1; size-=w+1; } else size =w; 
    } 
    if(size==8){ if(p[5] <= key){ p+=5; size=3; } else size=4; } 
    if(size==6){ if(p[4] <= key){ p+=4; size=2; } else size=3; } 
    if(size==5){ if(p[3] <= key){ p+=3; size=2; } else size=2; } 
    if(size==4){ if(p[3] <= key){ p+=3; size=1; } else size=2; } 
    if(size==2){ if(p[2] <= key){ p+=2; size=0; } else size=1; } 

    switch(size){ 
    case 7: if(p[4] <= key) p+=4; 
    case 3: if(p[2] <= key) p+=2; 
    case 1: if(p[1] <= key) p+=1; 
    } 
    *index=p-array; return p[0]==key; 
} 

[작은 숫자입니다 승 : w == pow (2, N) -1; 크기 < = 2 * (w + 1)]

int binsearch_7(arr_t array[], size_t size, arr_t key, size_t *index){ 
    if(!array || !size) return 0; 
    arr_t *p=array; 
    size_t w=(size-1)>>1; w|=w>>1; w|=w>>2; w|=w>>4; w|=w>>8; w|=w>>16; 
#if SIZE_MAX == UINT64_MAX 
    w|=w>>32; 
#endif 
    if(p[w]<key) p+=size-w-1; 
    switch(w){ 
#define C(n) case ((size_t)1<<n)-1: if(p[1<<(n-1)]<=key) p+=1<<(n-1); 
#if SIZE_MAX == UINT64_MAX 
               C(63) C(62) C(61) 
    C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51) 
    C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41) 
    C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32) 
#endif 
                  C(31) 
    C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21) 
    C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11) 
    C(10) C(9) C(8) C(7) C(6) C(5) C(4) C(3) C(2) C(1) 
#undef C 
    } 
    *index=p-array; return p[0]==key; 
} 

난으로부터 케이스 라벨 [의 단순화되었다 만들 었는지 마지막 단계 : '((이 size_t) 1 < < N) -1'에 ' n ']하지만 수정 된 코드가 이전 버전보다 이전 PC에서 느린 것으로 나타났습니다.

Answer 8

// Optimized Binary Search Implementation 
int binsearch(int* data, int size, int val) 
{ 
    int result = -1; 
    int start, mid, end; 
    start = 0; 
    end = size - 1; 
    mid = (start + end) >> 1; 
    while (start <= end && data[mid] != val) 
    { 
     if (data[mid] > val) 
      end = mid - 1; 
     else 
      start = mid + 1; 
     mid = (start + end) >> 1; 
    } 
    if (val == data[mid]) 
     result = mid; 
    return result; 
} 

Answer 9

그 운동 문제는 K & R 초판에 있습니다.

While(low <= high && arr[mid]!=num) 
{ 
    if(arr[mid] > num) 
    { 
     low = mid+1; 
    } 
    else 
    { 
     high = mid-1; 
    } 
    mid = (low+high)/2; 
} 

if(arr[mid] == num) 
{ 
    printf("found the ugly number"); 
    return mid; 
} 

Answer 10

BinarySearch = function (array, value) 
{ 
    var l = 0; 
    var r = array.length; 
    var mid; 
    while (l!=r) 
    { 
     mid = Math.round((r+l)/2)-1; 
     if(value > array[mid]) 
      l=mid+1; 
     else 
      r=mid; 
    } 
    if(array[mid]==value) 
     return mid; 
    else 
    { 
     if((mid < (array.length-1)) && (array[mid+1]==value)) 
      return mid+1; 
     else 
      return -1; // Not found 
    } 
} 

소스 : http://calcs.appspot.com/docview?id=agVjYWxjc3IPCxIIRG9jdW1lbnQY0w8M

Answer 11

bool binSearch(int array[], int key, int len) 
{ 
    int mid, low, high; 

    low = 0; 
    right = len - 1; 
    mid = low + (high-low)/2; 

    while ((low <= high) && (array[mid] != key)) { 
     if (key < array[mid]) { 
      high = mid - 1; 
     } else { 
      low = mid + 1; 
     } 
     mid = low + (high-low)/2; 
    } 

    if (array[mid] == key) { 
     return TRUE; 
    } 
    return FALSE; 
}