Thuật toán tìm kiếm nhị phân với javascript

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.”.