/codegym.vn/ - 141
Tìm phần tử có giá trị “35” trong mảng đã được sắp xếp theo trật tự tăng dần sau:
Đầu tiên, xác định chỉ số giữa của mảng theo công thức sau:
chỉ số giữa = (chỉ số đầu + chỉ số cuối) / 2;
Áp dụng cho mảng ở trên chúng ta xác định được chỉ số giữa là: (0+15)/2 = 7.5. Chúng
ta có thể làm tròn lên hoặc làm tròn xuống. Ở đây chúng ta sẽ làm tròn xuống, vậy chỉ
số giữa là 7 và giá trị của phần tử giữa mảng là 65.
Tiếp theo, chúng ta so sánh giá trị của phần tử giữa với giá trị cần tìm. Giá trị của
phần tử giữa là 65, giá trị của phần tử cần tìm là 35. Do đó không bằng nhau. Bởi vì
giá trị cần tìm nhỏ hơn nên giá trị cần tìm sẽ nằm ở mảng con bên trái phần tử giữa.
Chúng ta thay đổi (chỉ số cuối = chỉ số giữa - 1) và tiếp tục tìm kiếm chỉ số giữa.
chỉ số cuối = chỉ số giữa - 1
chỉ số giữa = (chỉ số đầu + chỉ số cuối) / 2
Bây giờ, chỉ số giữa được xác định là 3 và giá trị của phần tử giữa là 19. Do giá trị
cần tìm là 35, lớn hơn giá trị của phần tử giữa nên giá trị cần tìm sẽ nằm ở mảng con
bên phải phần tử giữa.
Tiếp tục tìm chỉ số giữa, lúc này chỉ số giữa là 5, và giá trị của phần tử giữa là 38. Do
giá trị cần tìm là 35, nhỏ hơn giá trị của phần tử giữa nên giá trị cần tìm sẽ nằm ở
mảng con bên trái phần tử giữa.
Tiếp tục tìm chỉ số giữa, lúc này chỉ số giữa là 4, và giá trị của phần tử giữa là 35,
bằng với giá trị cần tìm.
Chúng ta kết luận rằng, giá trị cần tìm là 35, được lưu trữ tại vị trí có chỉ số là 4 trong
mảng.
