Python triển khai thuật toán tìm kiếm nhị phân như thế nào?

Phạm vi

Bài viết này bao gồm các chủ đề dưới đây

• Tìm kiếm nhị phân trong python, hoạt động của tìm kiếm nhị phân trong python, tính chất của tìm kiếm nhị phân trong lập trình python
• Các bước đệ quy và triển khai tìm kiếm nhị phân trong python
• Các bước lặp và triển khai tìm kiếm nhị phân trong python
• Độ phức tạp về thời gian và không gian của tìm kiếm nhị phân trong python

Mỗi chủ đề được giải thích rõ ràng bằng sơ đồ và ví dụ bất cứ khi nào cần thiết

Giới thiệu về tìm kiếm nhị phân trong Python

Quá trình tìm kiếm một phần tử từ một tập hợp các phần tử được gọi là tìm kiếm. Chúng tôi có một số kỹ thuật hoặc cách tìm kiếm một phần tử trong số một số phần tử đã cho và những kỹ thuật này được gọi là thuật toán tìm kiếm. Tìm kiếm nhị phân là một trong những thuật toán tìm kiếm dễ dàng nhất. Hãy cùng chúng tôi tìm hiểu về tìm kiếm nhị phân trong python

Tìm kiếm nhị phân trong python là một kỹ thuật tìm kiếm hoạt động trên một mảng hoặc danh sách các phần tử được sắp xếp. Thay vì so sánh mọi phần tử của danh sách với phần tử được yêu cầu, thuật toán tìm kiếm nhị phân liên tục chia danh sách các phần tử thành các phân đoạn nhỏ hơn. Sau đó, nó tìm kiếm phần tử được yêu cầu trong các đoạn được chia

Hãy để chúng tôi thảo luận chi tiết về thuật toán tìm kiếm nhị phân

Làm việc của tìm kiếm nhị phân

Trước khi tìm hiểu khái niệm tìm kiếm nhị phân trong python, trước tiên chúng ta nên làm quen với kỹ thuật hay thuật toán chia để trị. Trong Chia để trị, như tên gợi ý, trước tiên, chúng ta chia bài toán lớn hơn thành các bài toán con nhỏ hơn và sau đó giải các bài toán con nhỏ hơn này. Cuối cùng, chúng ta sẽ kết hợp kết quả của các bài toán con nhỏ hơn để có được kết quả mong muốn

Như chúng ta đã thấy trước đó, tìm kiếm nhị phân chỉ hoạt động trên các mảng được sắp xếp, vì vậy nếu một mảng không được sắp xếp, trước tiên chúng ta sắp xếp mảng để thực hiện tìm kiếm nhị phân trong python

Đầu tiên, chúng ta sẽ so sánh phần tử ở giữa của mảng đã sắp xếp với phần tử cần sắp xếp. Nếu phần tử ở giữa là phần tử bắt buộc thì chúng ta không tiến hành thêm. Ngược lại, ta chia mảng thành hai phần theo kỹ thuật chia để trị

Nếu phần tử bắt buộc nhỏ hơn phần tử ở giữa thì chắc chắn phần tử đó nằm ở nửa đầu của mảng vì mảng đã được sắp xếp. Mặt khác, nếu phần tử được yêu cầu lớn hơn phần tử ở giữa, thì phần tử được yêu cầu phải có mặt trong nửa sau của mảng

Chúng tôi làm theo quy trình tương tự so sánh phần tử với phần tử ở giữa của mảng nhỏ hơn. Tìm kiếm nhị phân tiếp tục giảm mảng thành các mảng con nhỏ hơn cho đến khi chúng tôi tìm thấy phần tử cần thiết của mình

Thuộc tính của tìm kiếm nhị phân trong Python

• Tìm kiếm nhị phân tuân theo nguyên tắc của kỹ thuật phân chia và chinh phục
• Tìm kiếm nhị phân trong python chỉ hoạt động trên các mảng được sắp xếp hoặc danh sách các phần tử
• Nếu mảng không được sắp xếp, trước tiên chúng ta cần sắp xếp mảng để thực hiện tìm kiếm nhị phân trong python
• Tìm kiếm nhị phân tốt hơn tìm kiếm tuyến tính vì chúng ta không cần tìm kiếm toàn bộ mảng
• Tìm kiếm nhị phân trả về chỉ mục của phần tử được yêu cầu, nếu nó hiện diện
• Tìm kiếm nhị phân là một trong những thuật toán tìm kiếm nhanh nhất
• Đối với một tập hợp lớn các phần tử, tìm kiếm nhị phân trong python hoạt động tốt hơn tìm kiếm tuyến tính vì chúng tôi không cần tìm kiếm toàn bộ tập hợp các phần tử để tìm kết quả của mình

Hãy để chúng tôi lấy một ví dụ để hình dung hoạt động của tìm kiếm nhị phân

Giả sử chúng ta muốn tìm kiếm 115 trong mảng đã sắp xếp [13, 110, 115, 120, 135, 140, 260]

Đầu tiên, chúng ta sẽ đặt mức thấp ở chỉ số ngoài cùng bên trái là 0 và mức cao ở chỉ số ngoài cùng bên phải là 6. Sử dụng mức thấp và mức cao, bây giờ chúng ta sẽ tính mức trung bình [thấp + cao chia cho 2] cho ra chỉ số 3 với giá trị 120. Bây giờ, 120 lớn hơn phần tử i yêu cầu của chúng ta. e. 115

Vì mảng đã được sắp xếp, 115 phải có trong nửa đầu của mảng [phạm vi chỉ số từ thấp đến trung bình]. Vì vậy, chúng tôi chuyển sự chú ý sang nửa đầu của mảng bằng cách chuyển chỉ số cao sang [giữa - 1]

Tương tự, chúng ta có thể tìm thấy phần tử giữa của các mảng con, phần tử này nhỏ hơn 110 so với phần tử đích của bạn. Vì vậy, lần này chúng tôi chuyển chỉ số thấp của mình sang [giữa + 1]

Với chỉ số thấp hiện tại [i. e. , 2] và chỉ số cao hiện tại [i. e. , 2], chúng tôi tìm thấy chỉ số giữa của chúng tôi, là 2. 115 đang hiện diện tại mid index hiện tại. Vì vậy, chúng tôi đã tìm thấy phần tử cần thiết của mình ở chỉ mục thứ hai

Chúng ta có thể triển khai Tìm kiếm nhị phân trong python theo hai cách. đệ quy và lặp đi lặp lại

Tìm kiếm nhị phân đệ quy

Trước tiên hãy cho chúng tôi biết cách đệ quy. Giả sử chúng ta muốn tìm kiếm phần tử E trong mảng

Ghi chú

Khi một hàm gọi chính nó lặp đi lặp lại, nó được gọi là đệ quy. Mặt khác, khi một vòng lặp thực hiện lặp đi lặp lại cho đến khi điều kiện kiểm soát trở thành sai, chúng ta gọi đó là phép lặp

Chúng ta có thể gọi một hàm trên mảng với phần tử E được yêu cầu. Tìm kiếm nhị phân[mảng, E]. Hàm này sẽ trả về chỉ mục của phần tử E

Các bước liên quan đến phương pháp đệ quy

1. So sánh E với phần tử mid
2. Nếu E == mảng[giữa], thì chúng tôi trả về chỉ số giữa
3. Khác nếu E > mảng[giữa], gọi hàm Hàm tìm kiếm nhị phân ở nửa bên trái của mảng
4. Nếu không, chúng ta gọi hàm BinarySearch ở nửa bên phải của mảng

Ghi chú

Chúng ta phải thực hiện các bước trên bằng cách ghi nhớ điều kiện cơ bản là chỉ số thấp phải luôn nhỏ hơn hoặc bằng chỉ số cao

Mã số

def binary_search_recursive[array, low, high, E]:
    # Base Condition
    if high >= low:

        # First calculating the mid index
        mid = [high + low] // 2

        # If the element is present at the middle index, return the index as the answer.
        if array[mid] == E:
            return mid

        # If element is smaller than the middle element, then recursively checking the left sub array.
        elif array[mid] > E:
            return binary_search_recursive[array, low, mid - 1, E]

        # Else recursively checking the right sub array.
        else:
            return binary_search_recursive[array, mid + 1, high, E]

     # As the element is not present in the array, return -1.
    else:
        return -1


if __name__ == "__main__":
    array = [13, 110, 115, 120, 135, 140, 260]
    E = 115
    low = 0
    high = len[array] - 1

    index = binary_search_recursive[array, low, high, E]

    if index != -1:
        print[f"Element {E} is found in the array at index", str[index]]
    else:
        print[f"Element {E} is not present in the array."]


đầu ra

Element 115 is found in the array at index 2

Tìm kiếm nhị phân lặp

Bây giờ chúng ta hãy thảo luận về phương pháp lặp để thực hiện tìm kiếm nhị phân. Giả sử, chúng ta muốn tìm kiếm cùng một phần tử E trong mảng

Chúng ta có thể gọi một hàm trên mảng với phần tử E được yêu cầu. Tìm kiếm nhị phân[mảng, E]. Hàm này sẽ trả về chỉ số của phần tử E

Các bước liên quan đến phương pháp đệ quy

1. So sánh E với phần tử mid
2. Nếu E == mảng[giữa], thì chúng tôi trả về chỉ số giữa
3. Khác nếu E > array[mid], thì chúng ta chuyển chỉ số thấp sang mid + 1
4. Nếu không, chúng tôi chuyển chỉ số cao sang trung bình - 1

Mã số

def binary_search_iterative[array, low, high, E]:
    # Base Condition
    while high >= low:

        # First calculating the mid index
        mid = [high + low] // 2

        # The element is present at the middle index. Return the index as the answer.
        if array[mid] == E:
            return mid

        #  If the element is smaller than the middle element, then shift the low index to mid + 1.
        if array[mid] < E:
            low = mid + 1

        # Else shift the right index to mid - 1.
        else:
            high = mid - 1

     # As the element is not present in the array, return -1.
    else:
        return -1


if __name__ == "__main__":
    array = [13, 110, 115, 120, 135, 140, 260]
    E = 115
    low = 0
    high = len[array] - 1

    index = binary_search_iterative[array, low, high, E]

    if index != -1:
        print[f"Element {E} is found in the array at index", str[index]]
    else:
        print[f"Element {E} is not present in the array."]

đầu ra
Element 115 is found in the array at index 2

Tìm kiếm nhị phân phức tạp

Độ phức tạp về thời gian của tìm kiếm nhị phân trong python tốt hơn tìm kiếm tuyến tính vì chúng ta không cần tìm kiếm trên toàn bộ mảng. Chúng tôi chia mảng thành các mảng con nhỏ hơn một cách thông minh và nhận được câu trả lời của chúng tôi. Vì vậy, tìm kiếm nhị phân là một thuật toán nhanh hơn và hiệu quả hơn, nhưng nó chỉ hoạt động trên mảng đã sắp xếp

Khi phần tử mong muốn được tìm thấy trực tiếp ở chỉ số giữa, chúng ta sẽ có độ phức tạp thời gian tốt nhất i. e. , O[1]. Mặt khác, nếu chúng ta không thể tìm thấy phần tử cần thiết trong toàn bộ mảng, thì chúng ta sẽ nhận được độ phức tạp thời gian tồi tệ nhất, i. e. , O[log n]. Không gian không đổi

Độ phức tạp thời gian trung bình của tìm kiếm nhị phân trong python là O [log n]

Độ phức tạp không gian

Chúng tôi không cần bất kỳ biến hoặc cấu trúc dữ liệu bổ sung nào để tìm kết quả. Vì vậy, độ phức tạp không gian của tìm kiếm nhị phân là O[1]

Thuật toán tìm kiếm nhị phân được thực hiện như thế nào?

Các thuật toán được triển khai trong Python như thế nào?

Python có chức năng tìm kiếm nhị phân không?