Tìm kiếm truy vấn bằng tìm kiếm nhị phân trong JavaScript

Tìm kiếm truy vấn bằng tìm kiếm nhị phân trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một mảng các giá trị nguyên thủy đã sắp xếp làm đối số đầu tiên và một giá trị truy vấn làm đối số thứ hai. Sau đó, hàm của chúng ta nên sử dụng thuật toán Tìm kiếm nhị phân (Binary Search) để tìm xem truy vấn có tồn tại trong mảng hay không.

Nếu tồn tại, chúng ta trả về chỉ số của nó trong mảng, ngược lại trả về -1.

Ví dụ

Mã thực hiện như sau:

const arr = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23];
const binarySearch = (arr, query) => {
  let index = Math.floor(arr.length / 2);
  if (arr[index] === query){
    return index;
  }else if (arr.length === 1){
    return null;
  }else if (arr[index] < query) {
    arr = arr.slice(index + 1);
    let res = binarySearch(arr, query);
    if (res === null){
      return -1;
    }else {
      return index + 1 + res;
    };
  }else {
    let arr1 = arr.slice(0, index);
    return binarySearch(arr1, query);
  };
};
console.log(binarySearch(arr, 1));
console.log(binarySearch(arr, 7));
console.log(binarySearch(arr, 11));
console.log(binarySearch(arr, 12));
console.log(binarySearch(arr, 22));

Đầu ra

Kết quả trong console:

0 5 7 -1 13