Làm thế nào để xử lý bài toán tìm kiếm phần tử đầu tiên và cuối cùng xuất hiện của một giá trị trong mảng có chứa các phần tử trùng lặp bằng thuật toán Binary Search?

Question

Accepted Answer

Bản chất cơ chế hoạt động
Khi mảng chứa các phần tử trùng lặp, Binary Search tiêu chuẩn không đảm bảo trả về vị trí xuất hiện đầu tiên hoặc cuối cùng. Để giải quyết, chúng ta cần tùy chỉnh điều kiện khi tìm thấy giá trị arr[mid] == x:

Để tìm vị trí đầu tiên (First Occurrence): Khi arr[mid] == x, ta lưu lại vị trí mid và tiếp tục tìm kiếm ở nửa bên trái (right = mid - 1).
Để tìm vị trí cuối cùng (Last Occurrence): Khi arr[mid] == x, ta lưu lại vị trí mid và tiếp tục tìm kiếm ở nửa bên phải (left = mid + 1).

Độ phức tạp thời gian giữ nguyên ở mức O(log N).
Ví dụ triển khai bằng mã nguồn (Python)
def find_first(arr, x):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == x:
            result = mid
            right = mid - 1  # Tiếp tục tìm bên trái
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return result

def find_last(arr, x):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == x:
            result = mid
            left = mid + 1   # Tiếp tục tìm bên phải
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return result
Khi nào nên sử dụng?

Được ứng dụng rộng rãi trong các hệ thống cơ sở dữ liệu khi cần đếm số lần xuất hiện của một khóa (frequency count) hoặc tìm khoảng thời gian trong log hệ thống.

Kinh nghiệm thực chiến cho Junior
Nhiều lập trình viên Junior thường viết một hàm Binary Search chung rồi cố gắng sửa đổi cồng kềnh. Cách tối ưu và sạch sẽ nhất là viết riêng biệt hoặc truyền cờ (flag) điều kiện để tách biệt rõ ràng giữa việc tìm kiếm biên trái và biên phải.

Làm thế nào để xử lý bài toán tìm kiếm phần tử đầu tiên và cuối cùng xuất hiện của một giá trị trong mảng có chứa các phần tử trùng lặp bằng thuật toán Binary Search?

Bản chất cơ chế hoạt động

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi searching liên quan cùng chủ đề