0704. Tìm kiếm nhị phân
- Thẻ: Mảng, Tìm kiếm nhị phân
- Độ khó: Dễ
Tóm tắt đề bài
Mô tả: Cho một mảng đã được sắp xếp tăng dần và một giá trị mục tiêu .
Yêu cầu: Trả về vị trí của trong mảng, nếu không tìm thấy thì trả về -1.
Giải thích:
- Có thể giả sử tất cả các phần tử trong mảng đều không trùng lặp.
- Độ dài của mảng nằm trong khoảng từ .
- Mỗi phần tử trong mảng nằm trong khoảng từ .
Ví dụ:
- Ví dụ 1:
- Ví dụ 2:
Ý tưởng giải quyết
Ý tưởng: Tìm kiếm nhị phân
Đặt hai biến left
và right
là hai đầu mút của mảng, tức là left = 0
và right = len(nums) - 1
, đại diện cho khoảng tìm kiếm là (đóng ở bên trái và đóng ở bên phải).
Lấy vị trí giữa của hai biến left
và right
, tức là mid = (left + right) // 2
, trước tiên so sánh giá trị tại vị trí giữa nums[mid]
với giá trị mục tiêu target
.
- Nếu
target == nums[mid]
, trả về vị trí giữa trực tiếp. - Nếu
target > nums[mid]
, đặtleft = mid + 1
, sau đó tiếp tục tìm kiếm trong khoảng bên phải . - Nếu
target < nums[mid]
, đặtright = mid - 1
, sau đó tiếp tục tìm kiếm trong khoảng bên trái .
Ý tưởng: Mã giả
Ý tưởng: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .