ปัญหาในการใช้งานการค้นหาไบนารีจำนวนมาก?

เรารู้ว่าอัลกอริธึมการค้นหาแบบไบนารีนั้นดีกว่าอัลกอริธึมการค้นหาเชิงเส้น อัลกอริทึมนี้ใช้เวลาในการดำเนินการ 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;
}

อัลกอริธึมนี้จะทำงานได้ดีจนกว่าจุดเริ่มต้นและจุดสิ้นสุดจะมีจำนวนมาก หาก (start + end) มีค่าเกิน 2 ³² – 1 จากนั้นอาจส่งคืนตัวเลขติดลบหนึ่งตัวหลังจากสรุป และเนื่องจากตัวเลขติดลบไม่รองรับเป็นดัชนีอาร์เรย์ จึงอาจทำให้เกิดปัญหาได้

เพื่อแก้ปัญหานี้ มีหลายวิธี

วิธีที่ 1

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

วิธีที่สองจะทำงานเฉพาะใน Java เนื่องจาก C หรือ C++ ไม่มีโอเปอเรเตอร์>>>

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

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

เนื่องจาก>>> ไม่ได้รับการสนับสนุนใน C หรือ C++ เราจึงสามารถใช้วิธีการต่อไปนี้

วิธีที่ 3

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