Vấn đề trong nhiều triển khai Binary Search

Chúng ta biết thuật toán tìm kiếm nhị phân (binary search) tốt hơn tìm kiếm tuyến tính. Thuật toán này mất O(log n) thời gian để thực thi. Tuy nhiên hầu hết các trường hợp code triển khai có một số vấn đề. Hãy xem một hàm binary search như sau:

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 start và end đạt đến một số lớn. Nếu (start + end) vượt quá giá trị 2³² - 1 thì nó có thể trả về một số âm sau khi tràn. Và vì số âm không được hỗ trợ làm chỉ số mảng, nó có thể gây ra một số vấn đề.

Để khắc phục vấn đề này, có một vài cách khác nhau.

Phương pháp 1

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

Phương pháp thứ hai 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++, chúng ta có thể dùng phương pháp sau.

Phương pháp 3

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