Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> JavaScript

Tìm kiếm trong mảng bằng Binary Search trong JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số đã sắp xếp (tăng dần) arr làm đối số thứ nhất, và một số mục tiêu target làm đối số thứ hai. Hàm phải tìm target trong mảng arr dùng thuật toán binary search vì mảng đã sắp xếp.

Nếu target tồn tại, trả về chỉ số, ngược lại trả về -1.

Ví dụ, nếu đầu vào là:

Đầu vào

const arr = [3, 5, 7, 9, 11, 13, 15, 16, 18, 21, 24, 25, 28];
const target = 13;

Đầu ra

const output = 5;

Ví dụ

Dưới đây là mã thực hiện:

const arr = [3, 5, 7, 9, 11, 13, 15, 16, 18, 21, 24, 25, 28];
const target = 13;
const binarySearch = (arr = [], target) => {
  const helper = (low, high) => {
    if (low > high) { return -1; }
    const middle = Math.floor((low + high) / 2);
    if (arr[middle] === target) { return middle; }
    if (arr[middle] < target) {
      return helper(middle + 1, high);
    }
    return helper(low, middle - 1);
  };
  return helper(0, arr.length - 1);
};
console.log(binarySearch(arr, target));

Kết quả

5