Tìm kiếm nhị phân JavaScript: Hướng dẫn

Cách viết tìm kiếm nhị phân trong JavaScript

Thuật toán tìm kiếm làm cuộc sống lập trình viên dễ dàng hơn. Làm cho việc tìm mục cụ thể trong tập dữ liệu chục, trăm, nghìn mục dễ dàng.

Một dạng tìm kiếm phổ biến là tìm kiếm nhị phân. Tìm kiếm nhanh mục trong mảng. Mỗi lần tìm kiếm qua mục, giảm số mục còn lại phải tìm một nửa.

Trong hướng dẫn này, nói về tìm kiếm nhị phân là gì và cách hoạt động. Sau đó triển khai tìm kiếm nhị phân dùng hai cách: lặp (iterative) và đệ quy (recursive).

Hãy xây dựng thuật toán tìm kiếm nhị phân trong JavaScript!

Tìm kiếm nhị phân là gì?

Tìm kiếm nhị phân là thuật toán khoa học máy tính tìm mục trong mảng đã sắp xếp.

Nó bắt đầu giữa mảng và kiểm tra mục giữa nhỏ hơn, bằng, hay lớn hơn số bạn tìm.

Nếu số nhỏ hơn, thuật toán biết tìm nửa trái mảng, nơi số nhỏ hơn; nếu số lớn hơn, tập trung nửa phải. Tìm kiếm nhị phân chỉ hoạt động trên danh sách đã sắp xếp.

Tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuyến tính. Vì mỗi lần tìm kiếm, số mục còn lại giảm một nửa.

Cách dùng tìm kiếm nhị phân

Tìm kiếm nhị phân dễ hiểu khi nắm bắt.

Trước khi triển khai thuật toán, đi qua từng bước. Chúng ta tìm số "9" trong danh sách. Bắt đầu danh sách đã sắp xếp:

Đầu tiên, tìm số giữa và gán cho biến. Tìm bằng tính tổng số đầu và cuối chia hai. Gọi biến "middle":

8 là số giữa. Sau đó, so sánh số giữa với số tìm. Nếu số giữa bằng số tìm, tìm kiếm dừng.

Ví dụ này, 8 không bằng 9. Tìm kiếm tiếp tục.

Tiếp, so sánh số giữa lớn hơn 9 không. Không.

Điều này nói số tìm phải sau số giữa. 9 lớn hơn 8 trong danh sách sắp xếp. Chúng ta đặt số đầu bằng số giữa. Vì biết số tìm không trước số giữa.

Nếu số tìm nhỏ hơn, đặt số cuối bằng số giữa. Vì số nhỏ hơn số giữa, tập trung tìm nửa dưới danh sách.

Tìm kiếm nhị phân lặp lại nửa trên vì 9 lớn hơn 8:

Tìm số giữa lại. Là 9. So sánh 9 với số tìm. 9 bằng số tìm.

Nghĩa là tìm kiếm dừng. Chúng ta tìm thành công số 9!

Triển khai tìm kiếm nhị phân JavaScript

Tìm kiếm nhị phân triển khai dùng cách lặp hoặc đệ quy.

Tìm kiếm nhị phân lặp

Tìm kiếm nhị phân lặp dùng vòng lặp while tìm mục trong danh sách. Vòng lặp thực thi cho đến khi mục tìm thấy hoặc danh sách đã tìm hết.

Bắt đầu viết hàm tìm kiếm nhị phân:

function binarySearch(array, numberToFind) { let start = 0; let end = array.length - 1; while (start <= end) { let middle = Math.floor((start + end) / 2); if (array[middle] === numberToFind) { return middle; } else if (array[middle] < numberToFind) { start = middle + 1; } else { end = middle - 1; } } return -1; }

Đầu tiên định nghĩa hai biến: start và end. Theo dõi giá trị cao/thấp tìm kiếm làm việc. Dùng while chạy cho đến số đầu lớn hơn số cuối. Vòng lặp tính số giữa start và end trong danh sách.

Nếu số tìm bằng số giữa, số giữa trả về chương trình chính. Nếu số nhỏ hơn, giá trị start đặt bằng số giữa cộng một. So sánh dùng câu lệnh if.

Ngược lại, số cuối đặt bằng số giữa trừ một. Nếu số không tìm thấy sau while, -1 trả về. Gọi đây điều kiện cơ sở (base condition). Trong chương trình chính, kiểm tra số trả về bằng -1. Nếu đúng, nghĩa là số không tìm thấy.

Hàm chưa hoạt động. Cần chương trình chính gọi nó:

let numbers = [2, 6, 8, 9, 10]; let toFind = 9; let findNumber = binarySearch(numbers, toFind); if (findNumber !== -1) { console.log(`${toFind} đã tìm thấy tại vị trí ${findNumber}.`); } else { console.log(`${toFind} không tìm thấy.`); }

Định nghĩa danh sách số tìm kiếm và số muốn tìm. Gọi binarySearch. Tìm kiếm trả về -1 hoặc vị trí mục tìm.

-1 chỉ mục không tìm thấy. Nếu không tìm thấy, nội dung else thực thi. Ngược lại, if chạy.

Chạy mã:

9 đã tìm thấy tại vị trí 3.

Cho biết tìm kiếm thành công!

Tìm kiếm nhị phân đệ quy

Tìm kiếm nhị phân đệ quy coi đẹp hơn cách lặp. Vì tìm kiếm nhị phân thực hiện cùng phép toán lặp lại trên danh sách. Hành vi này triển khai bằng thuật toán đệ quy.

Mở file JavaScript mới dán mã:

function binarySearch(array, numberToFind, start, end) { if (start => end) { return -1; } let middle = Math.floor((start + end) / 2); if (array[middle] === numberToFind) { return middle; } else if (array[middle] < numberToFind) { return binarySearch(array, numberToFind, middle + 1, end); } else { return binarySearch(array, numberToFind, start, middle - 1); } }

Mã so sánh giống tìm kiếm đầu. Kiểm tra số giữa bằng, lớn hơn, nhỏ hơn số tìm.

Đầu hàm, dùng if kiểm tra số đầu lớn hơn số cuối. Nếu đúng, mục không tìm thấy trong danh sách chỉ định. Trả về -1 chương trình chính nếu vậy.

Nếu số tìm bằng số giữa, số giữa trả về chương trình chính. Nếu số tìm lớn hơn hoặc nhỏ hơn số giữa, binarySearch chạy lại. Tiếp tục cho đến khi mục tìm thấy hoặc danh sách tìm hết.

Chạy hàm, cần thay đổi chương trình chính:

let numbers = [2, 6, 8, 9, 10]; let toFind = 9; let findNumber = binarySearch(numbers, toFind, 0, numbers.length - 1); … 

Cần truyền thêm hai tham số: giá trị "start" và "end". Giá trị "start" = 0. Giá trị "end" = độ dài danh sách trừ một.

Chạy mã xem:

9 đã tìm thấy tại vị trí 3.

Tìm kiếm nhị phân thành công! Dùng cùng thuật toán cách lặp. Khác biệt là tìm kiếm nhị phân thực hiện bằng hàm gọi chính nó cho đến khi mục tìm thấy hoặc danh sách tìm hết, cái nào đến trước.

Kết luận

Tìm kiếm nhị phân làm dễ dàng tìm mục trong danh sách. Mỗi lần tìm kiếm thực thi, số mục còn lại giảm một nửa. Làm tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuyến tính.

Bây giờ bạn sẵn sàng triển khai tìm kiếm nhị phân JavaScript như chuyên gia!