704. Binary Search

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/binary-search/

Table of Contents

1. Cách tiếp cận vấn đề

Đây là một trong những bài toán căn bản nhất trong chủ đề tìm kiếm: Cho trước 1 mảng các số nguyên và 1 số target, trả về vị trí của số target đó trong mảng số nguyên nums, nếu không tìm thấy thì trả về -1. Ví dụ:

• Input: nums = [-1,0,3,5,9,12], target = 9
• Output: 4

Có thể dễ dàng thấy số target 9 nằm ở vị trí index thứ 4 (0 based) trong mảng input nums. Nếu target = 2 thì output sẽ là -1 do số 2 không tồn tại trong mảng input.

Bài toán yêu cầu ta giải với độ phức tạp thời gian là O(logn) - tức là không cho phép ta sử dụng giải thuật tìm kiếm tuyến tính Linear Search: Duyệt qua lần lượt từng phần tử và trả về kết quả ngay khi gặp được số target. Vì với cách tìm kiếm tuyến tính thông thường thì độ phức tạp sẽ là O(n), đòi hỏi ta phải suy nghĩ và tìm ra một giải pháp tối ưu hơn để thay thế.

Tuy nhiên trước tiên hãy tìm hiểu thêm các dữ kiện bên lề mà bài toán cung cấp:

• Tất cả các phần tử trong mảng nums là unique.
• Các phần tử được sắp xếp theo thứ tự tăng dần.

Tính chất unique giúp ta xác định được tính consistence của giải thuật, mỗi số target sẽ chỉ có 1 kết quả trả về là duy nhất và không đổi. Tuy nhiên tính chất quan trọng hơn là các phần tử được sắp xếp theo thứ tự tăng dần, hay nói rộng hơn là các phần tử có tính chất đơn điệu trong 1 khoảng nào đó của dãy số - 1 điều kiện tiên quyết để ta áp dụng giải thuật tìm kiếm nhị phân - Binary Search.

Chi tiết về Binary Search mình sẽ nói kỹ hơn ở bài viết khác, các bạn có thể tham khảo thêm tại đây để có kiến thức sơ lược về nó: Binary Search Algorithm – Iterative and Recursive Implementation

Về cơ bản, Binary Search duy trì 3 chỉ số:

• Left (hoặc low): Biên trái của khoảng tìm kiếm
• Right (hoặc high): Biên phải của khoảng tìm kiếm
• Mid: Giá trị nằm ở vị trí giữa của khoảng tìm kiếm, hay còn gọi là trung vị (lưu ý là khác với giá trị trung bình)

Binary Search sẽ áp dụng điều kiện tìm kiếm lên giá trị Mid, lúc này phần tử Mid sẽ chia mảng ra làm 2 khoảng, và giá trị tìm kiếm sẽ có thể nằm trong 1 trong 2 khoảng đó (phụ thuộc vào điều kiện tìm kiếm mà ta áp dụng lên giá trị Mid)

• Nếu giá trị tìm kiếm nằm trong khoảng trái thì ta sẽ loại bỏ khoảng phải, và thu hẹp lại khoảng tìm kiếm về khoảng bên trái. Ngược lại áp dụng tương tự nếu giá trị tiếm kiếm nằm trong khoảng phải.
• Giải thuật sẽ tiếp tục tìm kiếm trên khoảng còn lại cho tới khi khoảng tìm kiếm không hợp lệ nữa (rỗng) hoặc giá trị tìm kiếm đã được tìm thấy.

Như vậy ta đã nắm được dấu hiệu, cách nhận biết khi nào có thể áp dụng được Binary Search và 1 template có thể áp dụng được cho mọi bài toán, điểm khác nhau và khó nhất ở đây là làm sao xác định được:

Điều kiện tìm kiếm áp dụng cho giá trị Mid

Để từ đó có thể thu hẹp khoảng tìm kiếm về phía bên trái hoặc phải tương ứng.

Xét về time-complexity thì cơ bản ta cần tìm xem số lần mà ta cần để chia đôi khoảng tìm kiếm tạm gọi là x từ: n -> n/2 -> n/2^2 -> ... -> n/2^ x là bao nhiêu? Dễ thấy nó chính là log2(n), hay trong lập trình ta có thể rút gọn nó thành log(n) hay logn, và có thể ngầm hiểu là logarith với hệ số 2 của số n. Đó chính là lý do tại sao time-complexity của Binary Search là O(logn).

2. Solution & Phân Tích

Quay trở lại với bài toán của chúng ta, ta sẽ khởi tạo 2 biên left = 0 và right = n - 1 với n là số lượng phần tử trong mảng, thì điều kiện tìm kiếm áp dụng lên mid sẽ xoay quanh giá trị target của chúng ta:

• Nếu giá trị tại mid = target, ta sẽ trả về vị trí mid ngay lập tức, còn không thì:
• Nếu giá trị tại mid < target, chứng tỏ số target phải nằm ở bên khoảng phải mid, và ta có thể loại bỏ khoảng bên trái ngay lập tức bằng việc gán giá trị left = mid + 1;
• Nếu giá trị tại mid > target, chứng tỏ số target phải nằm ở bên khoảng trái mid, ta có thể loại bỏ khoảng bên phải tương tự bằng việc gán giá trị right = mid - 1;
• Lúc này ta đã có 1 khoảng tìm kiếm hoàn toàn mới và tiếp tục áp dụng logic tương tự cho khoảng đó cho tới khi
• Tìm được mid = target -> Trả về mid
• Hoặc left > right (khoảng tìm kiếm rỗng) thì dừng lại và trả về -1 (không tìm thấy)

Giải thuật vẫn sẽ áp dụng được cho mảng với 1 phần tử, left lúc này bằng right và giá trị mid sẽ trỏ về duy nhất phần tử đó và áp dụng logic tương tự.

Time-Complexity: O(logn)

Space-Complexity: O(1) - In-place algorithm

Với n là số lượng các phần tử trong mảng nums.

3. Code

Lưu ý chỗ tính giá trị mid = left + (right - left) / 2, nó sẽ tương đương với (left + right) / 2, tuy nhiên đây là best practice để giúp phòng tránh tràn số do phép tính left + right gây ra trong tường hợp left và right đạt giá trị quá lớn. Mình sẽ nói chi tiết hơn trong các bài toán sau, khi các bài toán đó có gài trường hợp này vào trong yêu cầu.

© hieulm2k | Buy me a coffee