Đầu tiên, thuật toán tìm kiếm nhị phân giả sử mảng a
đầu vào là mảng đã được sắp xếp theo thứ tự tăng dần, nếu mảng a
chưa được sắp xếp mà sử dụng thuật toán tìm kiếm nhị phân thì kết quả sẽ bị sai.
Ý tưởng cơ bản nhất của thuật toán tìm kiếm nhị phân là chia để trị, nói một cách đơn giản hơn là chia nhỏ mảng ra để tìm kiếm, thay vì duyệt trên toàn bộ mảng như thuật toán tìm kiếm tuần tự, thuật toán tìm kiếm nhị phân chia mảng thành những vùng nhỏ hơn và chọn lấy một vùng phù hợp để tìm kiếm trong đó thôi, bạn có thể thấy câu lệnh mid = (left + right) / 2
với mục đích để chia nhỏ mảng, nếu lần chia nhỏ mảng đầu tiên chưa tìm được phần tử cần tìm, tiếp tục chia nhỏ mảng cho đến khi không thể chia nhỏ được nữa, tức là left <= right
thì dừng, lúc này có thể trả về -1
để thông báo rằng không tìm thấy phần tử đó trong mảng.
Giả sử chúng ta có một mảng a
gồm các phần tử đã được sắp xếp như sau:
$$[1, 2, 3, 4, 5, 6, 7]$$
Chúng ta cần tìm phần tử 6 trong mảng?
Chia nhỏ mảng a
lần 1 bằng cách tính chỉ số giữa của mảng: mid = (0 + 7) / 2 = 3
. Ta có a[3] = 4
, kiểm tra xem x == a[mid]
hay không, tức là $6 == 4$ hay không? Không. Nhưng chúng ta biết rằng 6 > 4
, vậy tức là số 6
sẽ nằm bên phải số 4
, vậy có lý do gì để ta tìm kiếm bên trái mảng a
nữa không? Không, ta sẽ chỉ tìm vùng bên phải a
mà thôi tức là vùng có chỉ số từ mid
tới right
.
Vậy các câu lệnh:
else if (x < a[mid])
right = mid - 1;
else
left = mid + 1;
kiểm tra xem giá trị cần tìm lớn hơn hay nhỏ giá trị giữa mid
, nếu lớn hơn, cập nhật lại left = mid + 1
để chỉ tìm sang bên phải, nếu nhỏ hơn, cập nhật lại right = mid - 1
để chỉ tìm sang bên trái mảng.
Qua lần chia nhỏ đầu tiên, mảng a
sẽ còn:
$$[4, 5, 6, 7]$$
Tiếp tục chia nhỏ lần thứ hai, tương tự, tính chỉ số mid
, a[mid]
lúc này bằng 5, so sánh a[mid]
với số 6, 6 vẫn lớn hơn, vậy bỏ vùng bên trái tìm kiếm sang bên phải, mảng a
sau khi chia nhỏ lần thứ 2 sẽ còn:
$$[6, 7]$$
Tiếp tục chia nhỏ lần thứ ba, tính chí số mid
, a[mid] = 6
, so sánh a[mid]
với số 6, bằng nhau, trả về đã tìm được số 6 trong mảng.
Khi không thể chia được nữa, tức là left <= right
hay mảng chỉ còn 1 phần tử, mà phần tử đó lại không bằng với phần tử cần tìm, trả về -1
với ý nghĩa không tìm thấy.
Bạn có thể mô tả rõ hơn các giá trị tham số đầu vào của hàm
– xuans2huy xuans2huy 02.01.2019BinarySearch
được không?Hàm
– Member4478 Member4478 02.01.2019BinarySearch
nhận vào một mảnga
, có số lượng phần tử của mảng làn
và giá trị cần tìm làx
ạ.