Pattern · Tìm kiếm nhị phânTrung bình
Tìm Kiếm Trong Mảng XoaySearch in Rotated Sorted Array
Hiểu bài
Cho mảng số nguyên phân biệt nums đã sắp xếp tăng dần rồi xoay tại vị trí bí mật, và số nguyên target. Trả về chỉ số của target nếu tìm thấy, ngược lại trả về -1. Yêu cầu độ phức tạp O(log n).
Ví dụ:
ts
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
output = 4 // nums[4] = 0
nums = [4, 5, 6, 7, 0, 1, 2], target = 3
output = -1 // 3 không có trong mảng
nums = [1], target = 0
output = -1Mảng xoay có nghĩa là: tồn tại k sao cho nums = [nums[k], ..., nums[n-1], nums[0], ..., nums[k-1]].
Cách cơ bản
O(n) time, O(1) spacets
function search(nums: number[], target: number): number {
return nums.indexOf(target) // O(n) tuyến tính
}Vì sao cách này chậm:
Duyệt tuần tự vi phạm yêu cầu O(log n).
Cần khai thác tính chất: dù bị xoay, luôn có một nửa mảng còn nguyên thứ tự sắp xếp.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.