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 vấn đề đã cho.
Tuyên bố sự cố - Chúng tôi sẽ được cung cấp một danh sách đã được sắp xếp và chúng tôi 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, chúng tôi trả về chỉ số giữa.
-
Khác Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa mảng con bên phải sau phần tử giữa. Vì vậy, chúng tôi tái diễn cho nửa bên phải.
-
Khác (x nhỏ hơn) lặp lại cho nửa bên trái
Thuật toán đệ quy
Ví dụ
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
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 ("Element is present at index "+str(result))
else:
print ("Element is not present in array") Thuật toán lặp lại
Ví dụ
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
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 ("Element is present at index "+str(result))
else:
print ("Element is not present in array") Element is present at index 4
Kết luận
Trong bài viết này, chúng ta đã tìm hiểu về phương pháp áp dụng Tìm kiếm nhị phân.