많은 이진 검색 구현에 문제가 있습니까?

우리는 이진 검색 알고리즘이 선형 검색 알고리즘보다 낫다는 것을 알고 있습니다. 이 알고리즘을 실행하는 데 필요한 시간은 O(log n)입니다. 그러나 대부분의 경우 구현된 코드에 몇 가지 문제가 있습니다. 아래와 같이 이진 검색 알고리즘 함수를 고려해 보겠습니다. −

Example

int binarySearch(int array[], int start, int end, int key){
   if(start <= end){
      int mid = (start + end) /2); //mid location of the list
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}

이 알고리즘은 시작과 끝에서 큰 숫자에 도달할 때까지 잘 작동합니다. (시작 + 끝)이 2³² - 1 값을 초과하면 래핑 후 음수가 반환될 수 있습니다. 음수는 배열 인덱스로 지원되지 않으므로 이로 인해 몇 가지 문제가 발생할 수 있습니다.

이 문제를 해결하려면 몇 가지 방법이 있습니다.

방법 1

int mid = start + ((end - start) / 2)

두 번째 방법은 C 또는 C++에 >>> 연산자가 없기 때문에 Java에서만 작동합니다.

방법 2 (Java만 해당)

int mid = (start + end) >>> 1

C나 C++에서는 >>>를 지원하지 않으므로 다음 방법을 사용할 수 있습니다.

방법 3

int mid = ((unsigned int) low + (unsigned int) high) >> 1

위 내용은 많은 이진 검색 구현에 문제가 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!