Một vấn đề trong nhiều triển khai tìm kiếm nhị phân?

Chúng ta biết rằng thuật toán tìm kiếm nhị phân tốt hơn thuật toán tìm kiếm tuyến tính. Thuật toán này mất O (log n) lượng thời gian để thực thi. Mặc dù hầu hết các trường hợp, mã được triển khai có một số vấn đề. Chúng ta hãy xem xét một hàm thuật toán tìm kiếm nhị phân như bên dưới -

Ví dụ

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;
}

Thuật toán này sẽ hoạt động tốt cho đến khi bắt đầu và kết thúc đạt một số lượng lớn. Nếu (đầu + cuối) vượt quá giá trị 2 ³² - 1 thì nó có thể trả về một số âm sau khi kết thúc. Và vì các số âm không được hỗ trợ dưới dạng chỉ mục mảng, nên nó có thể gây ra một số vấn đề.

Để khắc phục sự cố này, có một số cách khác nhau.

Phương pháp 1

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

Phương thức thứ hai sẽ chỉ hoạt động trong Java vì C hoặc C ++ không có toán tử>>>.

Phương pháp 2 (chỉ Java)

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

Vì>>> không được hỗ trợ trong C hoặc C ++, nên chúng ta có thể sử dụng phương pháp sau.

Phương pháp 3

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