Trong b&agrave;i viết n&agrave;y, ch&uacute;ng ta sẽ c&ugrave;ng t&igrave;m hiểu về thuật to&aacute;n nhị ph&acirc;n v&agrave; c&aacute;ch viết chương tr&igrave;nh thực thi t&igrave;m kiếm nhị ph&acirc;n bằng ng&ocirc;n ngữ lập tr&igrave;nh Python. Trước ti&ecirc;n, ch&uacute;ng ta sẽ c&ugrave;ng t&igrave;m hiểu về c&aacute;ch hoạt động của thuật to&aacute;n n&agrave;y nh&eacute;!
<h2 style="text-align: justify;">1. C&aacute;ch thức hoạt động của t&igrave;m kiếm nhị ph&acirc;n</h2>
<ul style="text-align: justify;">
<li>Bước 1: Giả sử mảng cần t&igrave;m c&oacute; dạng như sau:</li>
</ul>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/6321fd55-f1f8-4b70-b601-61d79adf842c" alt="tim-kiem-nhi-phan-python-1" />
<ul style="text-align: justify;">
<li style="list-style-type: none;">
<ul>
<li>Gọi x = 6 l&agrave; phần tử cần t&igrave;m.</li>
</ul>
</li>
<li>Bước 2: Đặt hai con trỏ Low v&agrave; High lần lượt ở c&aacute;c vị tr&iacute; đầu ti&ecirc;n v&agrave; cuối c&ugrave;ng</li>
</ul>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/17caa6f3-eadf-4553-8a17-74162e5452e0" alt="tim-kiem-nhi-phan-python-2" />
<ul style="text-align: justify;">
<li>Bước 3: T&igrave;m phần tử giữa ở giữa của mảng, c&ocirc;ng thức x&aacute;c định chỉ số l&agrave; (arr[(high + low)/2]) = 8</li>
</ul>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/3efaaf1b-cc0f-4061-a721-a7d81eac02ab" alt="tim-kiem-nhi-phan-python-3" />
<ul style="text-align: justify;">
<li>Bước 4: Nếu x == mid, trả về chỉ số mid. Nếu kh&ocirc;ng, thực hiện so s&aacute;nh phần tử cần t&igrave;m với m.</li>
<li>Bước 5: Nếu x &gt; mid, thực hiện so s&aacute;nh x với phần tử ở giữa của c&aacute;c phần tử ở ph&iacute;a b&ecirc;n phải của phần tử mid. Điều n&agrave;y được thực hiện bằng c&aacute;ch đặt low = mid + 1.</li>
<li>Bước 6: Mặt kh&aacute;c, so s&aacute;nh x với phần tử ở giữa của c&aacute;c phần tử ở b&ecirc;n tr&aacute;i của phần tử mid. Điều n&agrave;y được thực hiện bằng c&aacute;ch thiết lập high = mid - 1.</li>
</ul>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/08ba9c9d-4f72-4d02-9663-fd61837a2a2d" alt="tim-kiem-nhi-phan-python-4" />
<ul style="text-align: justify;">
<li>Bước 7: Lặp lại từ bước 3 đến bước 6 cho đến khi low = high.</li>
<li>Bước 8: V&agrave; cuối c&ugrave;ng ta sẽ t&igrave;m được phần tử cần t&igrave;m l&agrave; 6.</li>
</ul>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/a16ed86e-49ef-415e-be54-30b3e0bc3ceb" alt="tim-kiem-nhi-phan-python-5" />
<h2 style="text-align: justify;"> 2. X&acirc;y dựng đoạn m&atilde; thực thi</h2>
Đoạn m&atilde; thực thi bằng ng&ocirc;n ngữ Python như sau:
<pre class="line-numbers language-python" tabindex="0"><code>#Trả về chỉ số của x trong arr nếu tồn tại, nếu kh&ocirc;ng c&oacute; sẽ trả về -1
def binary_search(arr, low, high, x):
 #Trường hợp cơ sở
 if high &gt;= low:
 mid = (high + low) // 2
 #Nếu phần tử c&oacute; tồn tại ở phần giữa của mảng
 if arr[mid] == x:
 return mid
 #Nếu phần tử nhỏ hơn mid, n&oacute; sẽ nằm ở ph&iacute;a b&ecirc;n tr&aacute;i của mảng điểm gốc l&agrave; tử phần tử mid
 elif arr[mid] &gt; x:
 return binary_search(arr, low, mid - 1, x)
 #Nếu kh&ocirc;ng, phần tử sẽ nằm b&ecirc;n phải
 else:
 return binary_search(arr, mid + 1, high, x)
 else:
 #Phần tử kh&ocirc;ng tồn tại trong tập hợp
 return -1

#Khởi tạo tập hợp
arr = [ 2, 3, 4, 10, 40 ]
x = 10

#Gọi h&agrave;m
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
 print("Phần tử cần t&igrave;m c&oacute; chỉ số l&agrave; ", str(result))
else:
 print("Phần tử cần t&igrave;m kh&ocirc;ng c&oacute; trong mảng.")</code></pre>
Kết quả đầu ra:
<img style="width: 100%;" src="http://tek4vn.2soft.top/public_files/a-png-57" alt="a" />
Trong đoạn m&atilde; b&ecirc;n tr&ecirc;n, ch&uacute;ng ta sẽ thực hiện phương ph&aacute;p h&agrave;m đệ quy. Việc đầu ti&ecirc;n cần l&agrave;m l&agrave; định nghĩa h&agrave;m binary_search để thực hiện c&ocirc;ng việc t&igrave;m kiếm với c&aacute;c tham số bao gồm:
<ol style="text-align: justify;">
<li style="font-weight: 400;" aria-level="1">Arr l&agrave; mảng chứa phần tử cần t&igrave;m</li>
<li style="font-weight: 400;" aria-level="1">Low l&agrave; chỉ số đầu ti&ecirc;n của mảng</li>
<li style="font-weight: 400;" aria-level="1">High l&agrave; chỉ số cuối c&ugrave;ng trong mảng</li>
<li style="font-weight: 400;" aria-level="1">X l&agrave; phần tử cần t&igrave;m</li>
</ol>
Một c&acirc;u lệnh điều kiện kiểm tra nếu chỉ số high lớn hơn low, ta sẽ thực hiện lấy ra gi&aacute; trị chỉ số mid = (high + low) // 2. V&agrave; nếu phần tử tại chỉ số mid bằng x, ta sẽ trả về vị tr&iacute; mid. Ngược lại, nếu phần tử tại chỉ số mid lớn hơn x (tức l&agrave; phần tử cần t&igrave;m sẽ nằm trong mảng con b&ecirc;n tr&aacute;i), ta sẽ thực hiện gọi h&agrave;m binary_search với tham số đầu v&agrave;o l&agrave; mảng arr, chỉ số low, chỉ số mid - 1 v&agrave; phần tử x. Ngược lại, phần tử cần t&igrave;m sẽ nằm trong mảng con b&ecirc;n phải, ch&uacute;ng ta sẽ thực hiện gọi h&agrave;m binary_search() với tham số đầu v&agrave;o l&agrave; mảng arr, chỉ số mid + 1, chỉ số high v&agrave; phần tử x. V&agrave; nếu kh&ocirc;ng t&igrave;m được phần tử x cần t&igrave;m, ta sẽ trả về gi&aacute; trị l&agrave; -1.
Như vậy, ch&uacute;ng ta đ&atilde; ho&agrave;n th&agrave;nh xong thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n bằng ng&ocirc;n ngữ ngữ lập tr&igrave;nh Python.

Admin

Xây dựng chương trình sử dụng thuật toán tìm kiếm nhị phân bằng Python

Cùng tác giả

Admin

Có liên quan