Cách tốt nhất để tìm kiếm một mục trong danh sách được sắp xếp bằng JavaScript là gì?

Liên quan đến các mảng được sắp xếp (có thể là theo thứ tự bất kỳ), tìm kiếm nhị phân là thuật toán tìm kiếm tối ưu hóa và hiệu quả nhất tồn tại. Chúng tôi bắt buộc phải viết một hàm tìm kiếm nhị phân để tìm kiếm một mảng các ký tự được sắp xếp cho một mục tiêu.

Sau đó, chúng ta nên đính kèm hàm đó vào thuộc tính nguyên mẫu của Đối tượng Mảng.

Ví dụ

Mã cho điều này sẽ là -

const arr = [2, 5, 8, 12, 14, 16, 17, 22, 26, 28, 35, 67, 78, 99];
const target = 22;
Array.prototype.binarySearch = function(target) {
   if ( !this.length ) { return false; }
   if ( this[0] === target ) { return true; }
   var i, mid,
      start = 0,
      end = this.length,
      c = false;
   while ( c = (i = this[mid = start+((end-start)>>1)]) !== target ) {
      i < target ? (start = mid) : (end = mid);
      if (start >= end - 1) { break; }
   }
   return !c;
};
console.log(arr.binarySearch(target));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

true