Binary search là thuật toán hiệu quả nhất cho mảng đã sắp xếp. Triển khai và gắn vào Array.prototype.
Ví dụ
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));
Kết quả
true