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

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 ta đượ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

Món ăn. 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

Bạn có biết cách tìm kiếm các mục trong danh sách Python và kiểm tra xem nó có hiện diện hay không? . “Tìm kiếm tuyến tính trong Python là gì?” . Vì vậy, hãy bắt đầu

Tìm kiếm trong Python là một kỹ thuật để tìm một phần tử cụ thể có hoặc không có trong danh sách đã cho

Có hai loại kỹ thuật tìm kiếm

• tìm kiếm tuyến tính
• Tìm kiếm nhị phân

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

Tìm kiếm tuyến tính là loại tìm kiếm cơ bản nhất được thực hiện. Nó còn được gọi là tìm kiếm tuần tự. Trong tìm kiếm này, chúng tôi kiểm tra từng phần tử trong danh sách đã cho cho đến khi tìm thấy kết quả phù hợp

Phương pháp này thường được sử dụng trong cuộc sống hàng ngày của chúng tôi như khi chúng tôi kiểm tra các mặt hàng tạp hóa, chúng tôi làm như vậy theo cách tìm kiếm tuyến tính

Về mặt kỹ thuật trong Python, Phương thức tìm kiếm này so sánh từng phần tử với giá trị cụ thể mà chúng tôi đang tìm kiếm. Nếu cả hai đều khớp, phần tử được tìm thấy và thuật toán trả về vị trí chỉ mục của khóa

Ưu điểm của tìm kiếm tuyến tính

• Chương trình tìm kiếm đơn giản
• Vài dòng mã
• Tốt nhất trong trường hợp phần tử tìm kiếm ở vị trí đầu tiên

Nhược điểm của tìm kiếm tuyến tính

• Không hiệu quả trong một số trường hợp
• Không thích hợp cho một danh sách dài tôi. e. , một danh sách có hơn 100 phần tử
• Trường hợp xấu nhất, phần tử tìm kiếm ở vị trí cuối cùng

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

Trước khi viết bất kỳ mã nào của chương trình, chúng ta phải biết thuật toán của nó. Vì vậy, hãy hiểu thuật toán của chương trình này

• Nhập danh sách các số
• Nhập mục cần tìm
• So sánh từng phần tử đó với từng phần tử của danh sách một
• Nếu tìm thấy kết quả khớp thì trả về True
• Nếu không tìm thấy kết quả khớp trong toàn bộ danh sách, hãy trả về Sai

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

Bây giờ chúng ta hãy xem chương trình Python để tìm kiếm tuyến tính

#Phương pháp 1. Tìm kiếm tuyến tính Sử dụng phạm vi []

list1 = [16, 2, 7, 5, 12, 54, 21, 9,  64, 12]
print['List has the items: ', list1]
Item = int[input['Enter a number to search for:  ']]
found = False
for i in range[len[list1]]:
    if list1[i] == Item:
        found = True
        print[Item, ' was found in the list at index  ', i]
        break
if found == False:
    print[Item, ' was not found in the list!']

Hãy xem đầu ra của mã Python sau đây sẽ là gì?

#Output
List has the items: [16, 2, 7, 5, 12, 54, 21, 9, 64, 12]
Enter a number to search for: 7
7 was found in the list at index 2

#Phương pháp 2. Tìm kiếm tuyến tính sử dụng def[]. [Chương trình tìm kiếm đơn giản và dễ dàng nhất]

def linear[x,y]:
    for i in x:
        if i ==y:
            return True
    return False
x=[12, 37, 45, 89, 1, 2, 34, 48, 9]
linear[x,2]
linear[x,9]
linear[x,5]

Hãy xem đầu ra của mã đã cho

#Output 
True
True
False

Tham khảo bài viết gốc tại

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

Bạn có biết cách tìm kiếm các mục trong danh sách Python và kiểm tra xem nó có hiện diện hay không?

đám mây punjabi. com

Thêm nội dung bằng tiếng Anh. io. Đăng ký nhận bản tin hàng tuần miễn phí của chúng tôi. Nhận quyền truy cập độc quyền để viết các cơ hội và lời khuyên trong cộng đồng của chúng tôi Discord

Phương pháp tìm kiếm tuyến tính hoạt động như thế nào?

Tìm kiếm tuyến tính được thực hiện như thế nào?