Trong bài viết này, chúng ta sẽ tìm hiểu về giải pháp và cách tiếp cận để giải quyết bài toán cho trước.
Đề bài − Chúng ta sẽ được cho một danh sách đã sắp xếp và cần tìm một phần tử với sự trợ giúp của tìm kiếm nhị phân.
Thuật toán
So sánh x với phần tử giữa.
Nếu x khớp với phần tử giữa, trả về chỉ số giữa.
Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa phải của mảng con sau phần tử giữa. Vì vậy, chúng ta đệ quy cho nửa phải.
Ngược lại (x nhỏ hơn) đệ quy cho nửa trái.
Thuật toán đệ quy
Ví dụ
def binarySearchAppr(arr, start, end, x):
# Kiểm tra điều kiện
if end >= start:
mid = start + (end - start) // 2
# Nếu phần tử có mặt ở giữa
if arr[mid] == x:
return mid
# Nếu phần tử nhỏ hơn giữa
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid - 1, x)
# Ngược lại phần tử lớn hơn giữa
else:
return binarySearchAppr(arr, mid + 1, end, x)
else:
# Phần tử không tìm thấy trong mảng
return -1
arr = sorted(['t', 'u', 't', 'o', 'r', 'i', 'a', 'l'])
x = 'r'
result = binarySearchAppr(arr, 0, len(arr) - 1, x)
if result != -1:
print("Phần tử có mặt tại chỉ số " + str(result))
else:
print("Phần tử không có trong mảng")
Thuật toán lặp
Ví dụ
def binarySearchAppr(arr, start, end, x):
# Kiểm tra điều kiện
if end >= start:
mid = start + (end - start) // 2
# Nếu phần tử có mặt ở giữa
if arr[mid] == x:
return mid
# Nếu phần tử nhỏ hơn giữa
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid - 1, x)
# Ngược lại phần tử lớn hơn giữa
else:
return binarySearchAppr(arr, mid + 1, end, x)
else:
# Phần tử không tìm thấy trong mảng
return -1
arr = sorted(['t', 'u', 't', 'o', 'r', 'i', 'a', 'l'])
x = 'r'
result = binarySearchAppr(arr, 0, len(arr) - 1, x)
if result != -1:
print("Phần tử có mặt tại chỉ số " + str(result))
else:
print("Phần tử không có trong mảng")
Kết quả
Phần tử có mặt tại chỉ số 4
Kết luận
Trong bài viết này, chúng ta đã tìm hiểu về cách tiếp cận để áp dụng Tìm kiếm nhị phân.