Tìm kiếm tuyến tính trong Python không có chức năng

Trong bài viết này, chúng ta sẽ tìm hiểu thuật toán tìm kiếm là gì và các loại thuật toán tìm kiếm i. Tìm kiếm tuyến tính và tìm kiếm nhị phân chi tiết. Chúng ta sẽ tìm hiểu thuật toán của họ cùng với mã python và các ví dụ chi tiết về các thuật toán tìm kiếm. Cuối cùng, chúng ta sẽ hiểu độ phức tạp về thời gian và ứng dụng của thuật toán tìm kiếm. Vậy hãy bắt đầu

Thuật toán tìm kiếm là gì?

Thậm chí không có một ngày nào mà chúng ta không muốn tìm kiếm điều gì đó trong cuộc sống hàng ngày của mình. Điều tương tự cũng xảy ra với hệ thống máy tính. Khi dữ liệu được lưu trữ trong đó và sau một khoảng thời gian nhất định, dữ liệu tương tự sẽ được người dùng truy xuất, máy tính sẽ sử dụng thuật toán tìm kiếm để tìm dữ liệu. Hệ thống nhảy vào bộ nhớ của nó, xử lý tìm kiếm dữ liệu bằng kỹ thuật thuật toán tìm kiếm và trả về dữ liệu mà người dùng yêu cầu. Do đó, thuật toán tìm kiếm là tập hợp các thủ tục được sử dụng để định vị dữ liệu cụ thể từ bộ sưu tập dữ liệu. Thuật toán tìm kiếm luôn được coi là thủ tục cơ bản của tính toán. Và do đó, người ta luôn nói rằng sự khác biệt giữa ứng dụng nhanh và ứng dụng chậm hơn thường được quyết định bởi thuật toán tìm kiếm mà ứng dụng sử dụng

Có nhiều loại thuật toán tìm kiếm có thể như tìm kiếm tuyến tính, tìm kiếm nhị phân, tìm kiếm nhảy, tìm kiếm theo cấp số nhân, tìm kiếm Fibonacci, v.v. Trong bài viết này, chúng ta sẽ tìm hiểu chi tiết về tìm kiếm tuyến tính và tìm kiếm nhị phân với các thuật toán, ví dụ và mã python

Tìm kiếm tuyến tính là gì?

Tìm kiếm tuyến tính còn được gọi là thuật toán tìm kiếm tuần tự để tìm phần tử trong tập hợp dữ liệu. Thuật toán bắt đầu từ phần tử đầu tiên của danh sách, bắt đầu kiểm tra mọi phần tử cho đến khi tìm thấy phần tử mong đợi. Nếu không tìm thấy phần tử trong danh sách, thuật toán sẽ duyệt qua toàn bộ danh sách và trả về “không tìm thấy phần tử”. Do đó, nó chỉ là một thuật toán tìm kiếm đơn giản

Ví dụ

Xét mảng phần tử dưới đây. Bây giờ chúng ta phải tìm phần tử a = 1 trong mảng được cung cấp bên dưới

Ta sẽ bắt đầu với phần tử đầu tiên của mảng, so sánh phần tử đầu tiên với phần tử cần tìm. Nếu không tìm thấy ta sẽ nhảy sang phần tử tiếp theo của mảng và so sánh với phần tử cần tìm i. e 'a'

Nếu phần tử được tìm thấy, chúng tôi sẽ trả về chỉ mục của phần tử đó, ngược lại, chúng tôi sẽ trả về 'không tìm thấy phần tử'

Thuật toán tìm kiếm tuyến tính

LinearSearch(array, key)
    for each element in the array
        if element == value
            return its index

Chương trình Python để tìm kiếm tuyến tính

def LinearSearch(array, n, k):

    for j in range(0, n):

        if (array[j] == k):

            return j

    return -1

 
array = [1, 3, 5, 7, 9]

k = 7
n = len(array)

result = LinearSearch(array, n, k)

if(result == -1):

    print("Element not found")

else:

    print("Element found at index: ", result)

đầu ra

Phần tử được tìm thấy tại chỉ mục. 3

Độ phức tạp về thời gian của tìm kiếm tuyến tính

Độ phức tạp thời gian chạy của thuật toán tìm kiếm tuyến tính là O(n) cho N số phần tử trong danh sách vì thuật toán phải đi qua từng phần tử để tìm phần tử mong muốn

Các ứng dụng của tìm kiếm tuyến tính

• Được sử dụng để tìm phần tử mong muốn từ bộ sưu tập dữ liệu khi tập dữ liệu nhỏ
• Các hoạt động tìm kiếm là ít hơn 100 mặt hàng

Tìm kiếm nhị phân là gì?

Tìm kiếm nhị phân được sử dụng với một khái niệm tương tự, tôi. e để tìm phần tử từ danh sách các phần tử. Các thuật toán tìm kiếm nhị phân nhanh và hiệu quả so với các thuật toán tìm kiếm tuyến tính. Điều quan trọng nhất cần lưu ý về tìm kiếm nhị phân là nó chỉ hoạt động trên danh sách các phần tử được sắp xếp. Nếu danh sách không được sắp xếp, thì trước tiên thuật toán sẽ sắp xếp các phần tử bằng thuật toán sắp xếp, sau đó chạy chức năng tìm kiếm nhị phân để tìm đầu ra mong muốn. Có hai phương pháp mà chúng ta có thể chạy thuật toán tìm kiếm nhị phân i. e, phương pháp lặp hoặc phương pháp đệ quy. Các bước của quy trình là chung cho cả hai phương pháp, sự khác biệt chỉ được tìm thấy trong cách gọi hàm

Thuật toán tìm kiếm nhị phân (Phương pháp lặp)

do until the pointers low and high are equal.

    mid = (low + high)/2

    if (k == arr[mid])

        return mid

    else if (k > arr[mid])           // k is on right side of mid

        low = mid + 1

    else                            // k is on left side of mid

        high = mid - 1

 

Thuật toán tìm kiếm nhị phân (Phương pháp đệ quy)

BinarySearch(array, k, low, high)

    if low > high
        return False 

    else
        mid = (low + high) / 2 

        if k == array[mid]
            return mid

        else if k > array[mid]        // k is on the right side
            return BinarySearch(array, k, mid + 1, high)

        else                               // k is on the right side
            return BinarySearch(array, k, low, mid - 1)

Ví dụ

Hãy xem xét mảng sau đây mà tìm kiếm được thực hiện. Gọi phần tử cần tìm là k=0

Bây giờ, chúng ta sẽ thiết lập hai con trỏ chỉ thấp đến vị trí thấp nhất trong mảng và cao đến vị trí cao nhất trong mảng

Bây giờ, chúng ta sẽ tìm phần tử ở giữa của mảng bằng thuật toán và đặt con trỏ ở giữa cho nó

Ta sẽ so sánh phần tử mid với phần tử cần tìm, nếu trùng sẽ trả về phần tử mid

Nếu phần tử cần tìm lớn hơn phần giữa, chúng ta sẽ đặt con trỏ thấp tới phần tử "giữa+1" và chạy lại thuật toán

Nếu phần tử cần tìm thấp hơn phần tử ở giữa, chúng ta sẽ đặt con trỏ cao đến phần tử "giữa 1" và chạy lại thuật toán

Chúng tôi sẽ lặp lại các bước tương tự cho đến khi con trỏ thấp gặp con trỏ cao và chúng tôi tìm thấy phần tử mong muốn

Mã Python cho tìm kiếm nhị phân (Phương pháp lặp)

def binarySearch(arr, k, low, high):
   
    while low <= high:
        mid = low + (high - low)//2
        if arr[mid] == k:
            return mid
        elif arr[mid] < k:

            low = mid + 1
        else:

            high = mid - 1
    return -1

arr = [1, 3, 5, 7, 9]

k = 5
result = binarySearch(arr, k, 0, len(arr)-1)

if result != -1:

    print("Element is present at index " + str(result))

else:

    print("Not found")

đầu ra

Yếu tố có mặt tại chỉ số 2

Mã Python cho tìm kiếm nhị phân (Phương pháp đệ quy)

def BinarySearch(arr, k, low, high):

    if high >= low:

        mid = low + (high - low)//2

        if arr[mid] == k:
            return mid

        elif arr[mid] > k:
            return BinarySearch(arr, k, low, mid-1)

        else:
            return BinarySearch(arr, k, mid + 1, high)

    else:
        return -1


arr = [1, 3, 5, 7, 9]
k = 5

result = BinarySearch(arr, k, 0, len(arr)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

đầu ra

Yếu tố có mặt tại chỉ số 2

Độ phức tạp về thời gian của Tìm kiếm nhị phân

Độ phức tạp thời gian chạy cho tìm kiếm nhị phân là khác nhau đối với từng kịch bản. Độ phức tạp thời gian trong trường hợp tốt nhất là O(1) có nghĩa là phần tử nằm ở giữa con trỏ. Độ phức tạp thời gian Trung bình và Trường hợp Xấu nhất là O(log n) có nghĩa là phần tử được tìm thấy nằm ở bên trái hoặc bên phải của con trỏ giữa. Ở đây, n cho biết số phần tử trong danh sách

Độ phức tạp không gian của thuật toán tìm kiếm nhị phân là O(1)

Các ứng dụng của tìm kiếm nhị phân

• Thuật toán tìm kiếm nhị phân được sử dụng trong các thư viện của Java, C++, v.v.
• Nó được sử dụng trong một chương trình bổ sung khác như tìm phần tử nhỏ nhất hoặc phần tử lớn nhất trong mảng
• Nó được sử dụng để thực hiện một từ điển

Sự khác biệt giữa Tìm kiếm tuyến tính và Tìm kiếm nhị phân

Tìm kiếm tuyến tính

Tìm kiếm nhị phân

Bắt đầu tìm kiếm từ phần tử đầu tiên và so sánh từng phần tử với phần tử được tìm kiếm

Tìm kiếm vị trí của phần tử được tìm kiếm bằng cách tìm phần tử ở giữa của mảng

Không cần danh sách phần tử được sắp xếp

Cần danh sách các phần tử được sắp xếp

Có thể được thực hiện trên mảng và danh sách liên kết

Không thể thực hiện trực tiếp trên danh sách liên kết

Lặp đi lặp lại trong tự nhiên

Chia để trị trong tự nhiên

dễ sử dụng

Khó thực hiện so với tìm kiếm tuyến tính

Ít dòng mã hơn

Nhiều dòng mã hơn

Ưu tiên cho một tập dữ liệu kích thước nhỏ

Được ưu tiên cho tập dữ liệu có kích thước lớn

Phần kết luận

Như đã nghiên cứu, thuật toán tìm kiếm tuyến tính và nhị phân có tầm quan trọng riêng tùy thuộc vào ứng dụng. Chúng ta thường cần tìm mục dữ liệu cụ thể trong số hàng trăm, hàng nghìn và hàng triệu bộ sưu tập dữ liệu và tìm kiếm tuyến tính và nhị phân sẽ giúp ích như vậy

Trường hợp tốt nhất cho tìm kiếm tuyến tính trong Python là gì?

Tìm kiếm đơn giản trong Python là gì?

Mã giả cho tìm kiếm tuyến tính là gì?

Là tìm kiếm tuyến tính giống như lực lượng vũ phu?