SERIES
Binary Search
Teach binary search beyond the textbook — applying it to rotated arrays, 2D matrices, and implicit search spaces.
Trong series nàyBẢN TIN
01
Binary Search: bãi mìn off-by-one
Binary search là một trong những thuật toán mà mọi người nghĩ rằng họ hiểu cho đến khi phải implement từ đầu. Logic là bốn dòng. Phần khó là các điều kiện biên — dùng lo <= hi hay lo < hi, và mid đi trái hay phải khi bỏ lỡ.13 thg 6, 2026 · 15 phút đọc · #00023
02
Search a 2D Matrix: làm phẳng chỉ số ma trận thành một binary search
Ma trận được đảm bảo sắp xếp theo từng hàng và theo cột — nghĩa là nếu bạn trải phẳng nó thành mảng 1D, nó hoàn toàn được sắp xếp. Binary search trên mảng 1D ảo, chuyển đổi mid trở lại (row, col): đó là toàn bộ thủ thuật.13 thg 6, 2026 · 13 phút đọc · #00024
03
Find Minimum in Rotated Sorted Array: nửa nào được sắp xếp?
Mảng được sắp xếp, sau đó xoay — phá vỡ bất biến binary search đơn giản. Cách sửa: so sánh mid với biên phải. Nếu mid nhỏ hơn right, minimum nằm ở nửa trái (bao gồm mid); nếu không thì nằm ở nửa phải (không bao gồm mid).13 thg 6, 2026 · 12 phút đọc · #00025
04
Search in Rotated Sorted Array: hai nửa đã sắp xếp, một điều kiện thêm
Sau khi xoay, ít nhất một trong hai nửa xung quanh mid luôn được sắp xếp. Đó là bất biến giữ cho binary search hoạt động. Bạn chỉ cần một kiểm tra thêm để biết nửa nào được sắp xếp, và sau đó target có trong nó không.13 thg 6, 2026 · 12 phút đọc · #00026
Đôi dòng ghi chép về những gì tôi đang xây
Nhận email khi tôi đăng bài mới — các bài kỹ thuật, không spam. Hủy đăng ký bất cứ lúc nào.