Tìm kiếm tuyến tính trong Python có nghĩa là gì?

Hoạt động tìm kiếm tuyến tính là hoạt động tìm kiếm đơn giản nhất. Trong hướng dẫn này, chúng tôi sẽ thực hiện thao tác tìm kiếm tuyến tính để khám phá vị trí chỉ mục của phần tử trong danh sách

Tìm kiếm tuyến tính - Giới thiệu cơ bản

Một phương pháp định vị các phần tử trong danh sách là tìm kiếm tuyến tính. Một tìm kiếm tuần tự là một tên khác cho nó. Bởi vì nó tìm kiếm phần tử được yêu cầu theo cách tuần tự. Nó đánh giá từng yếu tố liên quan đến giá trị mà chúng tôi đang tìm kiếm. Phần tử được phát hiện nếu cả hai khớp và thủ tục trả về vị trí chỉ mục của khóa

Hãy để chúng tôi hiểu sơ bộ về cách thực hiện tìm kiếm tuyến tính

1. Bắt đầu tìm kiếm của bạn với phần tử đầu tiên và kiểm tra khóa với từng phần tử trong danh sách
2. Nếu một phần tử được phát hiện, vị trí chỉ mục của khóa được trả về
3. Nếu phần tử không được phát hiện, giá trị trả về sẽ không xuất hiện

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

Đến đây, chúng ta đã hiểu sơ bộ về phép toán tìm kiếm tuyến tính. Chúng ta hãy xem Thuật toán theo mã để hiểu rõ hơn

1. Tạo một hàm linear_search[]
2. Khai báo 3 tham số mảng, độ dài mảng, số cần tìm
3. Khởi tạo vòng lặp for
4. Lặp lại từng phần tử và so sánh giá trị chính
5. Nếu phần tử có mặt trả về chỉ số
6. Khác trở lại không có mặt

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

Như đã thảo luận ở trên về thuật toán, bây giờ chúng ta hãy đi sâu vào phần lập trình của hoạt động tìm kiếm tuyến tính chịu ảnh hưởng của thuật toán

def linear_search[arr, a, b]:

    # Going through array 
    for i in range[0, a]:
        if [arr[i] == b]:
            return i
    return -1

arr = [9, 7, 5, 3, 1]
print["The array given is ", arr]
b = 5
print["Element to be found is ", b]
a = len[arr]
index = linear_search[arr, a, b]
if[index == -1]:
    print["Element is not in the list"]
else:
    print["Index of the element is: ", index]

Mảng đã cho là [9, 7, 5, 3, 1]
Phần tử cần tìm là 5
Chỉ số của phần tử là. 2

Phần kết luận

Trong hướng dẫn này, chúng tôi đã thực hiện thao tác tìm kiếm tuyến tính trong lập trình python với sự trợ giúp của tìm kiếm tuần tự

Trong khi lập trình chắc hẳn các bạn đã từng gặp trường hợp cần biết vị trí của một phần tử trong danh sách. Chúng ta có thể sử dụng thuật toán tìm kiếm tuyến tính cho mục đích này. Trong bài viết này, chúng tôi sẽ triển khai thuật toán tìm kiếm tuyến tính để tìm chỉ mục của một phần tử trong danh sách trong python

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

Trong thuật toán tìm kiếm tuyến tính, chúng ta bắt đầu từ chỉ số 0 của một danh sách và kiểm tra xem phần tử có mặt tại chỉ số hay không. Nếu phần tử có mặt tại chỉ mục, chúng tôi trả lại chỉ mục dưới dạng đầu ra. Mặt khác, chúng tôi chuyển sang chỉ mục tiếp theo cho đến khi chúng tôi tìm thấy phần tử đang được tìm kiếm hoặc chúng tôi đến cuối danh sách.  

Ví dụ: Giả sử rằng chúng tôi được cung cấp một danh sách myList=[1,23,45,23,34,56,12,45,67,24]

Bây giờ, chúng tôi muốn tìm kiếm chỉ mục của phần tử 12. Đối với điều này, chúng tôi sẽ bắt đầu từ chỉ số 0 và kiểm tra  xem 12 có ở đó hay không. Nếu có, chúng tôi sẽ trả về kết quả là 0 hoặc chúng tôi sẽ chuyển sang chỉ mục 1. Chúng tôi sẽ tiếp tục di chuyển theo cách này đến chỉ số 6 trong đó có 12. Sau khi kiểm tra xem 12 có ở chỉ số 6 không, chúng tôi sẽ trả về 6 dưới dạng đầu ra. Nếu bất kỳ phần tử nào không có mặt, chúng tôi sẽ trả về -1 sẽ xác định rằng phần tử đó không có trong danh sách

Có một cái nhìn tổng quan về hoạt động tìm kiếm tuyến tính, hãy xác định một thuật toán cho hoạt động tìm kiếm tuyến tính

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

Thuật toán tìm kiếm tuyến tính có thể được chỉ định như sau

Đầu vào cho thuật toán. Danh sách và phần tử cần tìm

đầu ra. Chỉ mục của phần tử nếu phần tử có mặt. Nếu không, -1

1. Bắt đầu từ chỉ số 0 của danh sách
2. Kiểm tra xem phần tử có ở vị trí hiện tại không
3. Nếu có, hãy trả lại chỉ mục hiện tại. Đi đến 8
4. Kiểm tra xem phần tử hiện tại có phải là phần tử cuối cùng của danh sách không
5. Nếu có, trả về -1. Đi đến 8. Nếu không, goto 6
6. Di chuyển đến chỉ mục tiếp theo của danh sách
7. quay lại 2
8. Dừng lại

Như chúng tôi đã xác định thuật toán cho tìm kiếm tuyến tính, hãy để chúng tôi thực hiện nó trong python

def LinearSearch[input_list: list, element: int]:
    list_len = len[input_list]
    for i in range[list_len]:
        if input_list[i] == element:
            return i
    return -1


myList = [1, 23, 45, 23, 34, 56, 12, 45, 67, 24]
print["Given list is:", myList]
position = LinearSearch[myList, 12]
print["Element 12 is at position:", position]

đầu ra

Given list is: [1, 23, 45, 23, 34, 56, 12, 45, 67, 24]
Element 12 is at position: 6

Hạn chế của thuật toán tìm kiếm tuyến tính

Một thuật toán tìm kiếm tuyến tính rất tốn kém về độ phức tạp thời gian. Nó có độ phức tạp O[n] trong trường hợp xấu nhất với n là số phần tử trong danh sách

Một nhược điểm nữa là nó không xét đến việc sắp xếp các phần tử trong danh sách. Nếu các phần tử được sắp xếp theo thứ tự tăng dần và chúng ta phải tìm kiếm phần tử lớn nhất thì sẽ luôn mất một số bước tối đa để cho ra kết quả

Tương tự, nếu một phần tử không có trong danh sách, nó sẽ thực hiện lại số bước tối đa để tạo ra kết quả vì nó sẽ duyệt qua từng phần tử của danh sách.  

Phần kết luận

Trong bài viết này, chúng ta đã thảo luận về thuật toán tìm kiếm tuyến tính. Chúng tôi cũng đã triển khai nó trong python. Để tìm hiểu thêm về lập trình python, bạn có thể đọc bài viết này về hiểu danh sách. Bạn cũng có thể thích bài viết này về danh sách liên kết trong Python

Có liên quan

Đào tạo Python được đề xuất

Khóa học. Python 3 cho người mới bắt đầu

Hơn 15 giờ nội dung video với hướng dẫn có hướng dẫn cho người mới bắt đầu. Tìm hiểu cách tạo các ứng dụng trong thế giới thực và nắm vững kiến ​​thức cơ bản

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

Tìm kiếm tuyến tính có nghĩa là gì?

Tìm kiếm tuyến tính với ví dụ là gì?

Tìm kiếm tuyến tính và tìm kiếm nhị phân trong Python có nghĩa là gì?