Cách viết mã tìm kiếm nhị phân trong JavaScript
Thuật toán tìm kiếm giúp cuộc sống của một lập trình viên trở nên dễ dàng hơn rất nhiều. Làm như vậy giúp bạn dễ dàng tìm thấy một mục cụ thể bên trong tập dữ liệu gồm hàng chục, hàng trăm hoặc hàng nghìn mục.
Một trong những hình thức tìm kiếm phổ biến nhất là tìm kiếm nhị phân. Tìm kiếm này nhanh chóng tìm thấy một mục trong một mảng. Mỗi khi tìm kiếm xem qua một mục, nó sẽ giảm một nửa số mục còn lại để tìm kiếm.
Trong hướng dẫn này, chúng ta sẽ nói về tìm kiếm nhị phân là gì và cách chúng hoạt động. Sau đó, chúng tôi sẽ tiếp tục triển khai tìm kiếm nhị phân bằng hai cách tiếp cận khác nhau:lặp lại và đệ quy.
Hãy xây dựng một 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à một thuật toán khoa học máy tính tìm kiếm một mục trong một mảng được sắp xếp.
Nó bắt đầu ở giữa một mảng và kiểm tra xem mục ở giữa có nhỏ hơn, bằng hoặc lớn hơn số mà bạn đang tìm kiếm hay không.
Nếu số nhỏ hơn, thuật toán biết tiếp tục tìm kiếm ở nửa bên trái của mảng, nơi có các số nhỏ hơn; nếu số lớn hơn, thuật toán sẽ tập trung vào nửa bên phải của mảng. Tìm kiếm nhị phân chỉ hoạt động trên danh sách được sắp xếp.
Tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuyến tính. Điều này là do mỗi khi thực hiện tìm kiếm, số lượng mục còn lại để tìm kiếm trong danh sách giảm đi một nửa.
81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia một cuộc thi đào tạo. Kết hợp với bootcamp ngay hôm nay.
Sinh viên tốt nghiệp bootcamp trung bình dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ.
Cách sử dụng tìm kiếm nhị phân
Tìm kiếm nhị phân rất dễ hiểu khi bạn hiểu rõ về nó.
Trước khi chúng tôi triển khai thuật toán tìm kiếm nhị phân, hãy cùng tìm hiểu từng bước một. Chúng ta sẽ tìm số "9" trong một danh sách. Hãy bắt đầu với một danh sách được sắp xếp:
| 2 | 6 | 8 | 9 | 10 |
Đầu tiên, chúng ta cần tìm số ở giữa và gán nó cho một biến. Điều này được tìm thấy bằng cách tính tổng của số đầu tiên và số cuối cùng rồi chia nó cho hai. Chúng tôi sẽ gọi biến này là "giữa":
| Bắt đầu | | Giữa | | Kết thúc |
| 2 | 6 | 8 | 9 | 10 |
8 là số giữa của chúng tôi. Sau đó, chúng ta có thể so sánh số giữa với số mà chúng ta đang tìm kiếm. Nếu số ở giữa bằng với số mà chúng tôi đang tìm kiếm, việc tìm kiếm của chúng tôi có thể dừng lại.
Trong ví dụ này, 8 không bằng 9. Tìm kiếm của chúng tôi tiếp tục.
Tiếp theo, chúng ta cần so sánh xem số ở giữa có lớn hơn 9. Không.
Điều này cho chúng ta biết rằng số mà chúng ta đang tìm kiếm phải sau số ở giữa. 9 lớn hơn 8 trong danh sách đã sắp xếp. Chúng ta sẽ đặt số bắt đầu bằng số ở giữa. Điều này là do chúng tôi biết rằng số mà chúng tôi đang tìm kiếm không đứng trước số ở giữa.
Nếu số chúng ta đang tìm kiếm nhỏ hơn, chúng ta sẽ đặt số cuối bằng số giữa. Vì số nhỏ hơn số ở giữa, chúng tôi có thể tập trung tìm kiếm vào nửa dưới của danh sách.
Tìm kiếm nhị phân lặp lại một lần nữa ở nửa trên của danh sách vì 9 lớn hơn 8:
| | | Bắt đầu | Giữa | Kết thúc |
| 2 | 6 | 8 | 9 | 10 |
Chúng tôi tìm lại số giữa. Đây là 9. Chúng ta có thể so sánh 9 với số mà chúng ta đang tìm kiếm. 9 bằng với số mà chúng ta đang tìm kiếm.
Điều này có nghĩa là tìm kiếm của chúng tôi có thể dừng lại. Chúng tôi đã tìm thấy thành công số 9 trong danh sách của mình!
Cách triển khai tìm kiếm nhị phân trong JavaScript
Tìm kiếm nhị phân có thể được thực hiện bằng cách sử dụng phương pháp lặp lại hoặc đệ quy.
Tìm kiếm nhị phân lặp lại
Tìm kiếm nhị phân lặp đi lặp lại sử dụng vòng lặp while để tìm một mục trong danh sách. Vòng lặp này sẽ thực hiện cho đến khi mục được tìm thấy trong danh sách hoặc cho đến khi danh sách được tìm kiếm.
Hãy bắt đầu bằng cách viết một hàm thực hiện tìm kiếm nhị phân của chúng ta:
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;
}
Chúng tôi bắt đầu bằng cách xác định hai biến:bắt đầu và kết thúc. Chúng theo dõi các giá trị cao nhất và thấp nhất mà tìm kiếm của chúng tôi đang làm việc. Chúng tôi sử dụng một vòng lặp while chạy cho đến khi số bắt đầu lớn hơn số kết thúc. Vòng lặp này tính toán số ở giữa giữa đầu và cuối trong danh sách.
Nếu số mà chúng ta đang tìm kiếm bằng số ở giữa, thì số ở giữa được trả về chương trình chính của chúng ta. Nếu số nhỏ hơn, giá trị bắt đầu được đặt bằng số ở giữa cộng với một. Các phép so sánh này được thực hiện bằng câu lệnh if.
Nếu không, số cuối được đặt bằng số ở giữa trừ đi một. Nếu số của chúng ta không được tìm thấy sau khi vòng lặp while chạy, -1 được trả về. Chúng tôi gọi đây là điều kiện cơ bản. Trong chương trình chính của chúng tôi, chúng tôi sẽ kiểm tra xem số trả về có bằng -1 hay không. Nếu đúng như vậy, có nghĩa là số của chúng tôi không thể được tìm thấy.
Chức năng của chúng tôi chưa hoạt động. Chúng ta cần viết một 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} has been found at position ${findNumber}.`);
} else {
console.log(`${toFind} has not been found.`);
}
Chúng tôi đã xác định một danh sách các số để tìm kiếm và số chúng tôi muốn tìm trong danh sách của mình. Tiếp theo, chúng ta đã gọi hàm tìm kiếm nhị phân. Điều này sẽ thực hiện tìm kiếm của chúng tôi. Tìm kiếm sẽ trả về -1 hoặc vị trí của mục mà chúng ta đang tìm kiếm.
-1 biểu thị rằng không thể tìm thấy một mục. Nếu một mục không được tìm thấy, nội dung của else của chúng tôi câu lệnh được thực thi. Nếu không, nội dung của if câu lệnh được chạy.
Hãy chạy mã của chúng tôi:
9 has been found at position 3.
Điều này cho chúng tôi biết rằng tìm kiếm của chúng tôi đã thành công!
Tìm kiếm nhị phân đệ quy
Tìm kiếm nhị phân đệ quy được coi là thanh lịch hơn tìm kiếm lặp lại. Điều này là do các tìm kiếm nhị phân thực hiện cùng một thao tác lặp đi lặp lại trên một danh sách. Hành vi này có thể được thực hiện bằng cách sử dụng một thuật toán đệ quy.
Mở một tệp JavaScript mới và dán vào mã này:
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);
}
}
Đoạn mã này thực hiện các phép so sánh giống như lần tìm kiếm đầu tiên của chúng tôi. Nó kiểm tra xem số ở giữa có bằng, lớn hơn hay nhỏ hơn số mà chúng ta đang tìm kiếm hay không.
Khi bắt đầu hàm của chúng ta, chúng ta đã sử dụng câu lệnh if để kiểm tra xem số bắt đầu có lớn hơn số kết thúc hay không. Nếu đúng như vậy, điều này có nghĩa là không thể tìm thấy mục của chúng tôi trong danh sách mà chúng tôi đã chỉ định. Chúng tôi trả về -1 cho chương trình chính nếu trường hợp này xảy ra.
Nếu số chúng ta đang tìm giống với số ở giữa, thì số ở giữa sẽ được quay lại chương trình chính. Nếu số mà chúng tôi đang tìm kiếm lớn hơn hoặc nhỏ hơn số ở giữa, thì chức năng Tìm kiếm nhị phân của chúng tôi sẽ được chạy lại. Điều này tiếp tục cho đến khi mục của chúng tôi được tìm thấy.
Để chạy chức năng này, chúng tôi cần thực hiện thay đổi đối với chương trình chính của mình:
let numbers = [2, 6, 8, 9, 10]; let toFind = 9; let findNumber = binarySearch(numbers, toFind, 0, numbers.length - 1); …
Chúng ta cần chuyển vào hai tham số bổ sung:giá trị “bắt đầu” và “kết thúc”. Giá trị của “start” bằng 0. Giá trị của “end” bằng độ dài của danh sách trừ đi một.
Hãy chạy mã của chúng tôi và xem điều gì sẽ xảy ra:
9 has been found at position 3.
Tìm kiếm nhị phân của chúng tôi đã thành công! Nó sử dụng cùng một thuật toán cơ bản như cách tiếp cận lặp lại. Sự khác biệt là tìm kiếm nhị phân được thực hiện bằng cách sử dụng một hàm gọi chính nó cho đến khi tìm thấy mục hoặc cho đến khi danh sách được tìm kiếm đầy đủ, tùy điều kiện nào đến trước.
Kết luận
Tìm kiếm nhị phân giúp bạn dễ dàng tìm thấy một mục trong danh sách. Mỗi khi thực hiện tìm kiếm, số lượng mục còn lại để tìm kiếm trong danh sách giảm đi một nửa. Điều này làm cho 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 trong JavaScript như một chuyên gia!