Thuật toán tìm kiếm nhị phân là một thuật toán tìm kiếm hiệu quả dùng để tìm kiếm phần tử trong một mảng đã được sắp xếp. Dưới đây là mã Javascript cho thuật toán tìm kiếm nhị phân:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Mã này sử dụng vòng lặp while để thực hiện tìm kiếm nhị phân trên mảng đã sắp xếp. Thuật toán sử dụng ba biến left
, right
và mid
để xác định phạm vi tìm kiếm. Ban đầu, left
được gán giá trị 0, right
được gán giá trị là độ dài của mảng trừ 1. Trong mỗi vòng lặp, chúng ta tính giá trị trung tâm của phạm vi tìm kiếm bằng cách lấy trung bình của left
và right
. Nếu giá trị tại mid
bằng với target
, chúng ta trả về vị trí mid
. Nếu giá trị tại mid
nhỏ hơn target
, chúng ta di chuyển left
lên mid + 1
. Nếu giá trị tại mid
lớn hơn target
, chúng ta di chuyển right
xuống mid - 1
. Nếu chúng ta không tìm thấy target
trong mảng, chúng ta trả về giá trị -1.
Mã có thể được sử dụng bằng cách gọi hàm binarySearch
và truyền mảng cần tìm kiếm và giá trị cần tìm vào như là các đối số đầu tiên và thứ hai, tương ứng. Ví dụ:
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let target = 6;
let result = binarySearch(arr, target); // 5
Để sử dụng thuật toán tìm kiếm nhị phân, trước hết bạn cần phải chắc chắn rằng mảng của bạn đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần. Nếu mảng chưa được sắp xếp, bạn có thể sử dụng thuật toán sắp xếp mảng trước.
Sau đó, bạn có thể sử dụng hàm binarySearch
để tìm kiếm phần tử trong mảng. Nếu phần tử được tìm thấy, hàm sẽ trả về chỉ số của phần tử trong mảng. Nếu không tìm thấy, hàm sẽ trả về giá trị -1.
Ví dụ, giả sử bạn có một mảng các số nguyên tăng dần từ 1 đến 100:
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100];
Bạn muốn tìm số 43 trong mảng này. Bạn có thể sử dụng hàm binarySearch
để tìm kiếm số 43 trong mảng này:
let target = 43;
let result = binarySearch(arr, target);
if (result === -1) {
console.log("Không tìm thấy số " + target + " trong mảng.");
} else {
console.log("Số " + target + " được tìm thấy tại vị trí " + result + ".");
}
Kết quả của đoạn mã này sẽ là: “Số 43 được tìm thấy tại vị trí 42.”.