Triển khai tìm kiếm nhị phân trong JavaScript để trả về chỉ mục nếu số được tìm kiếm tồn tại

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một mảng số được sắp xếp làm đối số đầu tiên và một số tìm kiếm làm đối số thứ hai.

Nếu số tìm kiếm tồn tại trong mảng, chúng ta cần trả về chỉ số của nó trong mảng, nếu không, chúng ta cần trả về -1.

Chúng ta phải làm điều này bằng cách sử dụng thuật toán tìm kiếm nhị phân. Thuật toán tìm kiếm nhị phân về cơ bản là một thuật toán chia và chinh phục, trong đó đệ quy chia mảng thành các nửa cho đến khi nó chuyển đổi với một phần tử singleton.

Việc sắp xếp mảng là cần thiết của thuật toán tìm kiếm nhị phân trong trường hợp này, vì nó giúp chúng ta dễ dàng quyết định phần nào sẽ chia.

Ví dụ

const arr = [-3, -1, 4, 7, 9, 11, 14, 22, 26, 28, 36, 45, 67, 78, 88, 99];
const binarySearch = (arr = [], num) => {
   let l = 0;
   let r = arr.length - 1;
   while(l <= r){
      const mid = Math.floor((l + r) / 2); if(num == arr[mid]){
         return mid;
      }
      else if(num < arr[mid]){
         r = mid - 1;
      }
      else{
         l = mid + 1;
      };
   };
   return -1
};
console.log(binarySearch(arr, 22));
console.log(binarySearch(arr, 56));
console.log(binarySearch(arr, 11));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

7
-1
5