Danh sách tìm kiếm nhị phân của chuỗi Python

Bài viết sau đây cung cấp một phác thảo cho tìm kiếm nhị phân trong Python. Tìm kiếm nhị phân là một thuật toán tìm kiếm được sử dụng để tìm một phần tử cụ thể trong một mảng được sắp xếp. Nó tìm kiếm bằng cách liên tục chia mảng thành 2 nửa trong mỗi lần lặp. Nó hoạt động theo cách tiếp cận phân chia và chinh phục. So sánh phần tử tìm kiếm được thực hiện với phần tử ở giữa của mảng và sau đó quyết định phần nào của mảng sẽ tiếp tục tìm kiếm. Tìm kiếm nhị phân được coi là một trong những thuật toán tốt nhất khi có 1000 phần tử và người dùng muốn tìm kiếm và lấy chỉ mục của một phần tử cụ thể. Điều kiện duy nhất để sử dụng tìm kiếm nhị phân trong một chương trình là các phần tử cần được sắp xếp để thực hiện nó

cú pháp

Bắt đầu khóa học phát triển phần mềm miễn phí của bạn

Phát triển web, ngôn ngữ lập trình, kiểm thử phần mềm và những thứ khác

Dưới đây là cú pháp cơ bản của việc sử dụng tìm kiếm nhị phân trong Python

Gói phát triển phần mềm tất cả trong một(hơn 600 khóa học, hơn 50 dự án)

Giá
Xem khóa học

600+ Khóa học trực tuyến. hơn 50 dự án. Hơn 3000 giờ. Giấy chứng nhận có thể kiểm chứng. Truy cập Trọn đời
4. 6 (83.403 xếp hạng)

b_search(array, 0, array_len-1, element):
mid = low+high //2
if array[mid] == element:
# do something
elif array[mid] <= element:
b_search (array, mid+1, array_len-1, element)
else
b_search(array, 0, mid-1, element)
else
#do something (element not found)

Ở đâu,

b_search. chức năng tìm kiếm tìm kiếm nhị phân có tất cả logic

mảng. danh sách có tất cả các phần tử được lưu trữ theo thứ tự được sắp xếp

Tìm kiếm nhị phân hoạt động như thế nào trong Python?

Như chúng ta đã hiểu Tìm kiếm nhị phân dùng để tìm kiếm phần tử trong mảng đã sắp xếp. Nó liên tục chia mảng thành hai nửa bằng cách so sánh nó với phần tử ở giữa và tiến tới một nửa với xác suất của phần tử. Do đó, nó tiếp tục cho đến khi tìm thấy phần tử cần tìm. Dưới đây đưa ra là quy trình từng bước về cách tìm kiếm nhị phân hoạt động trong Python

1. Sắp xếp các phần tử của mảng theo thứ tự tăng dần (nếu không)

2. Giả sử chúng ta có danh sách các phần tử được sắp xếp như

và phần tử cần tìm là 10

3. Chỉ số bắt đầu được coi là 'L' và chỉ số cuối cùng là 'R'. Vì vậy, bây giờ phần tử ở giữa được tính là

mid = (L+H)/2

Trong ví dụ trên,

mid = (0+7)/2
mid= 3

1. Bây giờ, sự so sánh được thực hiện giữa phần tử ở giữa, tôi. e. , 40 (trong trường hợp trên) và phần tử cần tìm là i. e. , 10. Nếu phần tử được tìm kiếm bằng phần tử giữa, tìm kiếm thành công và có thể kết thúc tìm kiếm tiếp theo

2. Nếu phần tử cần tìm nhỏ hơn phần tử mid thì ta sẽ loại bỏ các giá trị lớn hơn phần tử mid của mảng, i. e. , tất cả các giá trị từ 50 đến 'H' cuối cùng đều bị loại bỏ. Bây giờ H = giữa 1. Một lần nữa bước 3 và 4 được lặp lại

• Theo ví dụ trên, bây giờ H = 30, L=10
• Một lần nữa mid được tính toán, bây giờ mid= (0+2)/2 = 1
• So sánh được thực hiện giữa 10 (Phần tử cần tìm) và giữa, tôi. e. , 20. Vì chúng không bằng nhau và 10 nhỏ hơn giữa, chúng tôi di chuyển sang phía bên trái của mảng, v.v.

3. Nếu phần tử cần tìm cao hơn phần tử mid ta sẽ loại bỏ các giá trị nhỏ hơn phần tử mid, i. e. , mảng bên trái sẽ bị loại bỏ. Bây giờ L = giữa+1. Một lần nữa bước 3 và 4 được lặp lại

ví dụ

Tìm kiếm nhị phân có thể được thực hiện bằng cách sử dụng phương pháp Lặp lại hoặc phương pháp Đệ quy để tìm phần tử trong mảng. Nhưng chúng tôi đã sử dụng phương pháp Đệ quy để thực hiện tìm kiếm nhị phân bên dưới

# Using the recursive function to implement binary search
def b_search(binary_array, L, H, ele):
# Checking the list is sorted or not
    if L <= H:
#finding the middle element of the array
        mid = (L + H) // 2
# If element to be searched is equal to middle element, it returns the index and program terminates
        if binary_array[mid] == ele:
            return mid
# If the element to be searched is smaller than the mid, search continues to the left side of the array.
        elif binary_array[mid] > ele:
#now the H = mid-1 in the new search
            return b_search(binary_array, L, mid - 1, ele)
# If the element is larger than the mid, search continues to the right side of the array
        else:
#now the L = mid+1 in the new search
            return b_search(binary_array, mid + 1, H, ele)
    else:
#If the element to be searched is not present in the list
        return -1
# Array containing the items in the sorted order.
binary_array = [12, 30, 56, 67, 87, 90, 101]
#element to be searched
ele = 90
# Calling the binary search function created above by passing the array, starting index,last index and the element to be searched
result = b_search(binary_array, 0, len(binary_array)-1, ele)
if result != -1:
print("Congratulations!! Your Element is present at "+ str(result+1)+ " position")
else:
print("Sorry!! Element you are searching is not present in the list")

đầu ra

Giải trình

• Trong ví dụ trên, đầu tiên, binary_array có tất cả các phần tử theo thứ tự được sắp xếp được xác định
• Phần tử cần tìm được xác định trong biến 'ele', là 90
• Hàm có tên 'b_search' được gọi bằng cách chuyển mảng phần tử ở trên (binary_array), chỉ mục bắt đầu (là 0 trong mọi trường hợp), chỉ mục cuối cùng (là độ dài của mảng-1) và phần tử (ele) đến
• Kết quả được lưu trữ trong một biến có tên là 'kết quả'
• Trong hàm 'b_search', phần tử ở giữa 'giữa' được tính bằng cách sử dụng (thấp + cao)/2
• Nếu các câu lệnh elif và other được sử dụng để so sánh phần tử giữa phần tử 'mid' với phần tử 'ele' được tìm kiếm
• Các điều kiện tìm kiếm nhị phân đơn giản được áp dụng cho các hành động được thực hiện nếu giá trị ở giữa nhỏ hơn phần tử được tìm kiếm (làm cho L = mid+1)
• Nếu giá trị ở giữa cao hơn phần tử cần tìm (đặt H = mid-1)
• Chỉ mục ‘Mid’ được trả về nếu tìm thấy phần tử và -1 nếu không tìm thấy phần tử cần tìm trong danh sách
• Một thông báo thích hợp được in trên bảng điều khiển theo kết quả được ghi trong biến 'kết quả'

Sự kết luận

Mô tả ở trên giải thích rõ ràng tìm kiếm nhị phân là gì và cách thức hoạt động của nó trong Python. Tìm kiếm nhị phân được coi là một trong những thuật toán tìm kiếm tốt nhất khi các phần tử được lưu trữ theo thứ tự đã sắp xếp. Hơn nữa, nó khá dễ thực hiện. Tốc độ tìm kiếm rất nhanh vì nó bỏ qua các so sánh không cần thiết bằng cách xem xét danh sách duy nhất gần với phần tử được tìm kiếm

Bài viết được đề xuất

Đây là hướng dẫn về Tìm kiếm nhị phân trong Python. Ở đây chúng tôi thảo luận về cách Tìm kiếm nhị phân hoạt động trong Python cùng với các ví dụ và kết quả đầu ra. Bạn cũng có thể xem các bài viết sau để tìm hiểu thêm –

Bạn có thể tìm kiếm nhị phân một danh sách các chuỗi không?

Tìm kiếm nhị phân có thể được sử dụng cho chuỗi Python không?

Tìm kiếm nhị phân có hoạt động trên mảng chuỗi được sắp xếp không?

Tìm kiếm nhị phân được thực hiện như thế nào trong Python?