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

Chúng ta cần viết hàm JavaScript nhận vào mảng số đã sắp xếp làm đối số đầu tiên và 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, trả về chỉ số của nó, ngược lại trả về -1.

Phải dùng thuật toán tìm kiếm nhị phân. Thuật toán này là chia để trị, đệ quy chia mảng thành hai nửa cho đến khi hội tụ về phần tử đơn lẻ.

Sắp xếp mảng là cần thiết cho tìm kiếm nhị phân, vì nó giúp dễ dàng quyết định phần nào để 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));

Kết quả

Kết quả in ra console:

7 -1 5