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

우리는 이진 탐색 알고리즘이 선형 탐색 알고리즘보다 낫다는 것을 알고 있습니다. 이 알고리즘은 실행하는 데 O(log n) 시간이 걸립니다. 대부분의 경우 구현된 코드에는 몇 가지 문제가 있습니다. 아래와 같은 하나의 이진 검색 알고리즘 기능을 고려해 보겠습니다. -

예시

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(자바만 해당)

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

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

방법 3

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