Thuật toán JavaScript: Tìm kiếm nhị phân

Tìm kiếm nhị phân giả định mảng (hoặc bất kỳ cấu trúc dữ liệu nào khác) bạn đang tìm kiếm được sắp xếp theo thứ tự.

Chúng ta bắt đầu với mảng và mục chúng ta cần tìm kiếm.

Chúng ta nhìn vào giữa mảng. Chúng ta lấy số phần tử và chia nó cho 2. Hãy tưởng tượng chúng ta có một phần của mảng ở bên trái và phần kia ở bên phải.

Nếu món đồ chúng ta có thấp hơn món đồ chúng ta đang tìm, thì nó phải ở đúng phần, vì vậy chúng ta hoàn toàn có thể bỏ phần bên phải.

Sau đó, chúng tôi thực hiện hành động tương tự, chia phần bên phải của mảng làm 2, nhìn vào mục ở giữa và chúng tôi loại bỏ một phần của mảng.

Cuối cùng, bạn sẽ nhận được vật phẩm (hoặc bạn sẽ trở lạinullnếu mục không được tìm thấy).

Cuối cùng, nếu mảng có 8 mục, chúng tôi tìm mục đó trong nhiều nhất 4 bước.

Nếu mảng có 32 mục, chúng tôi có tối đa 6 bước trong trường hợp xấu nhất. So với 32 trong tìm kiếm tuyến tính, đó là một sự tối ưu hóa rất lớn!

Tìm kiếm nhị phân cóO(log n) phức tạp.

Dưới đây là một cách triển khai khả thi của nó:

const binarySearch = (list, item) => {
  let low = 0
  let high = list.length - 1

while (low <= high) { const mid = Math.floor((low + high) / 2) const guess = list[mid]

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">===</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">mid</span>
}

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">&gt;</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#a6e22e">high</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>
} <span style="color:#66d9ef">else</span> {
  <span style="color:#a6e22e">low</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>
}

}

return null //if not found }

Cái này hoạt động ra sao? Chúng tôi nhận đượclistmảng và giá trị mục mà chúng tôi đang tìm kiếm. Sau đó, chúng tôi khởi tạolowgiá trị ban đầu bằng 0 vàhighgiá trị của chỉ mục cuối cùng trong danh sách. Đầu tiên chúng tôi xem xét mục ở giữa và nếu đó là thứ chúng tôi đang tìm kiếm, chúng tôi sẽ trả lại và chúng tôi đã hoàn tất. Nếu không, chúng tôi đặtlowhoặc làhighgiá trị để chỉ nhìn vào phần bên trái hoặc bên phải của mảng và chúng tôi lặp lại quy trình cho đến khi chúng tôi tìm thấy mục.

Chúng tôi trả về chỉ mục của mục trong mảng:

console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0
console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4

Chúng tôi trở lạinullnếu phần tử không được tìm thấy:

console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null

Tải xuống miễn phí của tôiSổ tay dành cho Người mới bắt đầu JavaScript


Các hướng dẫn js khác: