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