ปัญหาในหลายการนำ Binary Search มาใช้งาน

เรารู้ว่า Binary Search ดีกว่า Linear Search ใช้เวลา O(log n) แต่โค้ดที่นำไปใช้งานจริงหลายกรณีมีปัญหา พิจารณาโค้ด Binary Search ตัวอย่าง:

ตัวอย่างที่มีปัญหา

int binarySearch(int array[], int start, int end, int key) {
    if (start <= end) {
        int mid = (start + end) / 2; // mid location
        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;
}

อัลกอริทึมนี้ทำงานได้จนกว่า start และ end จะใหญ่พอที่ (start + end) เกิน 2³²-1 แล้วจะได้ค่าลบหลัง wrap around และ index ติดลบจะทำให้ error

วิธีแก้ปัญหา

วิธี 1 (แนะนำ)

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

วิธี 2 (Java เท่านั้น)

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

ตัวดำเนินการ >>> (unsigned right shift) ไม่มีใน C/C++

วิธี 3 (C/C++)

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