Binary Search

Q: Độ phức tạp thời gian của tìm kiếm nhị phân là gì?

Thời gian O(log n) . Mỗi lần so sánh, phạm vi có thể chứa giá trị mục tiêu giảm đi một nửa, vì vậy danh sách có 10^9 phần tử cần tối đa 30 lần so sánh. Phiên bản lặp dùng thêm O(1) không gian.

Q: Nên dùng tìm kiếm nhị phân theo cách lặp hay đệ quy?

Cả hai đều đúng và đều chạy trong thời gian O(log n) . Phiên bản đệ quy dùng bộ nhớ ngăn xếp O(log n) ; vòng lặp di chuyển lo và hi dùng O(1) . Người phỏng vấn thường mong đợi vòng lặp.

Q: Làm thế nào để tránh tràn số khi tính chỉ số ở giữa?

Viết mid = lo + (hi - lo) / 2 thay vì (lo + hi) / 2 . Cả hai đều cho cùng một chỉ số, nhưng với số nguyên 32 bit, tổng lo + hi sẽ bị tràn khi các chỉ số vượt khoảng 1.07 × 10^9 . Python và Ruby có số nguyên không giới hạn, nên cách viết ngắn gọn này an toàn trong các ngôn ngữ đó.

DễTìm kiếm nhị phân

+10

Bạn có một danh sách số nguyên nums được sắp xếp theo thứ tự tăng dần, không có giá trị nào lặp lại, và một số nguyên target. Hãy trả về chỉ số của target trong nums, tính từ 0, hoặc -1 nếu giá trị đó không có trong danh sách. Mục tiêu là đạt độ phức tạp thời gian O(log n), nghĩa là bạn không thể kiểm tra từng phần tử.

Hàm

search(nums: integer-array, target: integer) → integer

numsinteger-array: danh sách đã sắp xếp gồm các số nguyên phân biệt
targetinteger: giá trị cần tìm
Trả vềinteger: chỉ số của target trong nums, hoặc -1 nếu không có

Ràng buộc

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums được sắp xếp theo thứ tự tăng dần nghiêm ngặt, vì vậy mỗi giá trị chỉ xuất hiện một lần.

Ví dụ

Đầu vào: nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
Đầu ra: 4
Giải thích: nums[4] có giá trị là 9. Phép tìm kiếm xét chỉ số 3 (giá trị 4, quá nhỏ), rồi đến chỉ số 5 (giá trị 15, quá lớn), sau đó đến chỉ số 4, nơi phép tìm kiếm tìm thấy 9.

Đầu vào: nums = [1, 3, 5, 8, 13, 21]target = 10
Đầu ra: -1
Giải thích: 10 nằm giữa 8 và 13, nhưng cả hai đều không phải 10, nên 10 không có trong danh sách. Phạm vi tìm kiếm thu hẹp lại cho đến khi lo vượt qua hi, rồi hàm trả về -1.

Câu hỏi mở rộng

Nếu các giá trị trong nums có thể lặp lại, làm thế nào để bạn trả về chỉ số đầu tiên của target mà vẫn giữ độ phức tạp O(log n)?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Danh sách đã được sắp xếp, vì vậy chỉ cần so sánh một lần với phần tử ở giữa là bạn biết nửa nào vẫn có thể chứa target. Loại bỏ một nửa số ứng viên ở mỗi bước nghĩa là danh sách có 10^4 phần tử cần nhiều nhất 14 lần so sánh thay vì 10.000.

Quét từ trái sang phải

Ý tưởng

So sánh từng phần tử với target theo thứ tự và trả về phần tử khớp đầu tiên, hoặc -1 sau vòng lặp. Cách này đúng với mọi danh sách, dù đã sắp xếp hay chưa.

Cách này không tận dụng thứ tự, nên danh sách có 10^4 phần tử có thể cần đến 10.000 phép so sánh: O(n), không phải O(log n) như bài yêu cầu.

Thuật toán

Với mỗi chỉ số i từ 0 đến n-1, hãy so sánh nums[i] với target.
Nếu chúng bằng nhau, hãy trả về i.
Sau vòng lặp, hãy trả về -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Tìm kiếm nhị phân với hai chỉ số

Ý tưởng

Duy trì hai chỉ số, lo và hi, với một cam kết: nếu target có trong danh sách, chỉ số của nó nằm trong khoảng giữa hai chỉ số này, tính cả hai đầu. Khi nums[mid] nhỏ hơn target, mọi phần tử đến mid cũng nhỏ hơn, vì danh sách đã được sắp xếp, nên lo có thể chuyển đến vị trí sau mid. Vì lý do tương tự, nếu nums[mid] lớn hơn target, hãy chuyển hi đến vị trí trước mid. Cam kết vẫn được giữ sau mỗi lần di chuyển.

Nếu không tìm thấy target, phạm vi thu hẹp lại cho đến khi lo vượt qua hi. Khi đó phạm vi rỗng, nên cam kết cho biết target không có ở đâu trong danh sách. Mỗi bước giảm một nửa phạm vi, nên vòng lặp chạy tối đa khoảng log2(n) + 1 lần, với bộ nhớ bổ sung cho hai chỉ số.

Thuật toán

Đặt lo = 0 và hi = n-1.
Khi lo ≤ hi, tính mid = lo + (hi - lo) / 2.
Nếu nums[mid] bằng target, trả về mid.
Nếu nums[mid] < target, đặt lo = mid + 1; nếu không, đặt hi = mid - 1.
Khi vòng lặp kết thúc, trả về -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1  # nums[mid] and everything left of it is too small
        else:
            hi = mid - 1  # nums[mid] and everything right of it is too big
    return -1

Lỗi thường gặp và trường hợp biên

Lặp khi lo < hi trong khi hi bắt đầu ở chỉ số cuối cùng. Vòng lặp dừng lại khi còn một ứng viên chưa được kiểm tra, nên nums = [5] với target = 5 trả về -1.
Chuyển đến lo = mid hoặc hi = mid trong một khoảng bao gồm cả hai đầu. Khi lo và hi nằm cạnh nhau, mid bằng lo và khoảng không bao giờ thu hẹp: vòng lặp vô hạn.
Trả về lo khi không tìm thấy target. Sau vòng lặp, lo là vị trí chèn, một chỉ số hợp lệ, chứ không phải -1.
Quên dịch chỉ số trong Lua và R. Danh sách của chúng bắt đầu từ 1, nên chỉ số bạn trả về bằng vị trí trừ 1.

Câu hỏi thường gặp3

Độ phức tạp thời gian của tìm kiếm nhị phân là gì?

Thời gian O(log n). Mỗi lần so sánh, phạm vi có thể chứa giá trị mục tiêu giảm đi một nửa, vì vậy danh sách có 10^9 phần tử cần tối đa 30 lần so sánh. Phiên bản lặp dùng thêm O(1) không gian.

Nên dùng tìm kiếm nhị phân theo cách lặp hay đệ quy?

Cả hai đều đúng và đều chạy trong thời gian O(log n). Phiên bản đệ quy dùng bộ nhớ ngăn xếp O(log n); vòng lặp di chuyển lo và hi dùng O(1). Người phỏng vấn thường mong đợi vòng lặp.

Làm thế nào để tránh tràn số khi tính chỉ số ở giữa?

Viết mid = lo + (hi - lo) / 2 thay vì (lo + hi) / 2. Cả hai đều cho cùng một chỉ số, nhưng với số nguyên 32 bit, tổng lo + hi sẽ bị tràn khi các chỉ số vượt khoảng 1.07 × 10^9. Python và Ruby có số nguyên không giới hạn, nên cách viết ngắn gọn này an toàn trong các ngôn ngữ đó.

def search(nums, target):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

nums = [-7, -2, 0, 4, 9, 15, 23]
target = 9

Đầu ra mong đợi