Tìm kiếm nhị phân trên mảng đã xoay (Rotated Sorted Array)
Một mảng số nguyên được sắp xếp tăng dần gồm các phần tử phân biệt bị xoay tại một trục ẩn (ví dụ: [0, 1, 2, 4, 5, 6, 7] xoay thành [4, 5, 6, 7, 0, 1, 2]).
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: binary search.
Nội dung đề bài
Mục tiêu kiến thức
- Nắm vững nguyên lý chia để trị của tìm kiếm nhị phân cải tiến.
- Xác định nửa tăng dần (sorted half) của mảng xoay tại mỗi bước lặp.
- Đạt độ phức tạp thời gian nghiêm ngặt O(log N).
Mô tả bài toán
Một mảng số nguyên được sắp xếp tăng dần gồm các phần tử phân biệt bị xoay tại một trục ẩn (ví dụ: [0, 1, 2, 4, 5, 6, 7] xoay thành [4, 5, 6, 7, 0, 1, 2]).
Viết hàm search_rotated_sorted_array(nums: list[int], target: int) -> int:
- Tìm kiếm chỉ số của
targettrong mảngnums. - Nếu tìm thấy, trả về chỉ số (0-indexed). Nếu không tìm thấy, trả về
-1. - Thuật toán phải có độ phức tạp thời gian O(log N).
Input
- Tham số:
nums: list[int],target: int.
Output
- Trả về:
int(chỉ số hoặc -1).
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
search_rotated_sorted_array([4, 5, 6, 7, 0, 1, 2], 0)Output
4Giải thích
Hàm được gọi với các tham số mẫu trên và trả về kết quả chính xác theo yêu cầu.
Ví dụ 2
Input
search_rotated_sorted_array([4, 5, 6, 7, 0, 1, 2], 3)Output
-1Giải thích
Hàm được gọi với bộ tham số thứ hai và trả về kết quả tương ứng theo thiết kế.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.