Cấu trúc dữ liệu nào được sử dụng để tìm kiếm tuyến tính trong python?

Chương trình sau đại học. Phát triển web đầy đủ ngăn xếp

Tìm kiếm là gì?

Tìm kiếm là quá trình tìm nạp một phần tử cụ thể trong một tập hợp các phần tử. Tập hợp có thể là mảng hoặc danh sách liên kết. Nếu bạn tìm thấy phần tử trong danh sách, quá trình được coi là thành công và nó trả về vị trí của phần tử đó

Và ngược lại nếu không tìm thấy phần tử thì coi như việc tìm kiếm không thành công

Hai chiến lược tìm kiếm nổi bật được sử dụng rộng rãi để tìm một mục cụ thể trong danh sách. Tuy nhiên, thuật toán được chọn được xác định bởi tổ chức của danh sách

1. Tìm kiếm tuyến tính
2. Tìm kiếm nhị phân

Tiếp tục trong hướng dẫn này, bạn sẽ hiểu chính xác thuật toán tìm kiếm tuyến tính là gì

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

Tìm kiếm tuyến tính, thường được gọi là tìm kiếm tuần tự, là kỹ thuật tìm kiếm cơ bản nhất. Trong loại tìm kiếm này, bạn xem qua toàn bộ danh sách và cố gắng tìm nạp một phần tử phù hợp. Nếu bạn tìm thấy kết quả phù hợp, thì địa chỉ của phần tử đích phù hợp sẽ được trả về.  

Ngược lại, nếu không tìm thấy phần tử thì nó trả về giá trị NULL.  

Sau đây là cách tiếp cận từng bước được sử dụng để thực hiện Thuật toán tìm kiếm tuyến tính

Các thủ tục để thực hiện tìm kiếm tuyến tính như sau

Bước 1. Đầu tiên, đọc phần tử tìm kiếm [Target element] trong mảng

Bước 2. Trong bước thứ hai so sánh phần tử tìm kiếm với phần tử đầu tiên trong mảng

Bước 3. Nếu cả hai đều khớp, hiển thị "Đã tìm thấy phần tử mục tiêu" và chấm dứt chức năng Tìm kiếm tuyến tính.  

Bước 4. Nếu cả hai đều không khớp, hãy so sánh phần tử tìm kiếm với phần tử tiếp theo trong mảng.  

Bước 5. Trong bước này, lặp lại bước 3 và 4 cho đến khi phần tử tìm kiếm [Target] được so sánh với phần tử cuối cùng của mảng

Bước 6 - Nếu phần tử cuối cùng trong danh sách không khớp, Chức năng tìm kiếm tuyến tính sẽ bị chấm dứt và thông báo "Không tìm thấy phần tử" sẽ được hiển thị

Cho đến nay, bạn đã khám phá định nghĩa cơ bản và thuật ngữ làm việc của Thuật toán tìm kiếm tuyến tính.  

Thuật toán và mã giả của thuật toán tìm kiếm tuyến tính

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

Tìm kiếm tuyến tính [ Array Arr, Value a ] // Arr là tên của mảng và a là phần tử được tìm kiếm

Bước 1. Đặt i thành 0 // i là chỉ số của một mảng bắt đầu từ 0

Bước 2. ifi > n thì chuyển sang bước 7 // n là số phần tử của mảng

Bước 3. nếu Arr[i] = a thì chuyển sang bước 6

Bước 4. Đặt i thành i + 1

Bước 5. Chuyển đến bước 2

Bước 6. In phần tử a được tìm thấy tại chỉ mục i và chuyển sang bước 8

Bước 7. Không tìm thấy phần tử in

Bước 8. Lối ra

Mã giả của thuật toán tìm kiếm tuyến tính

Bắt đầu

linear_search [ Mảng , giá trị ]

Đối với mỗi phần tử trong mảng

Nếu [phần tử được tìm kiếm == giá trị]

Trở lại vị trí than thở được tìm kiếm

kết thúc nếu

kết thúc cho

kết thúc

Theo hiểu biết của bạn về thuật toán tìm kiếm tuyến tính và mã giả, trong phần tiếp theo, bạn sẽ thực hiện thực tế thuật toán

cũng đọc. Thuật toán là gì?

Khóa học mới. Phát triển Full Stack cho người mới bắt đầu

Ví dụ về thuật toán tìm kiếm tuyến tính

Xét một mảng có kích thước 7 với các phần tử 13, 9, 21, 15, 39, 19 và 27 bắt đầu bằng 0 và kết thúc bằng kích thước trừ một, 6

Phần tử tìm kiếm = 39

Bước 1. Phần tử tìm kiếm 39 được so sánh với phần tử đầu tiên của một mảng, đó là 13

Không tìm thấy kết quả phù hợp, bây giờ bạn chuyển sang phần tử tiếp theo và thử thực hiện so sánh

Bước 2. Bây giờ, phần tử tìm kiếm 39 được so sánh với phần tử thứ hai của một mảng, 9

Vì cả hai đều không khớp, bạn sẽ tiếp tục tìm kiếm

Bước 3. Bây giờ, phần tử tìm kiếm 39 được so sánh với phần tử thứ ba, là 21

Một lần nữa, cả hai phần tử đều không khớp, bạn chuyển sang phần tử tiếp theo sau

Bước 4;

Vì cả hai đều không khớp, bạn chuyển sang phần tử tiếp theo

Bước 5. Tiếp theo, phần tử tìm kiếm 39 được so sánh với phần tử thứ năm 39

Một kết hợp hoàn hảo được tìm thấy, bạn ngừng so sánh bất kỳ phần tử nào nữa và chấm dứt Thuật toán tìm kiếm tuyến tính và hiển thị phần tử được tìm thấy ở vị trí 4

Tiếp theo là phần triển khai thực tế, bạn sẽ chuyển sang phần phức tạp của thuật toán tìm kiếm tuyến tính

Độ phức tạp của thuật toán tìm kiếm tuyến tính

Bạn gặp phải ba vấn đề phức tạp khác nhau khi thực hiện Thuật toán tìm kiếm tuyến tính, chúng được đề cập như sau

1. Trường hợp tốt nhất
2. Trường hợp xấu nhất
3. trường hợp trung bình

Bạn sẽ tìm hiểu về từng người trong số họ chi tiết hơn một chút

Trường hợp phức tạp nhất

• Phần tử đang được tìm kiếm có thể được tìm thấy ở vị trí đầu tiên
• Trong trường hợp này, tìm kiếm kết thúc với một so sánh thành công duy nhất
• Do đó, trong trường hợp tốt nhất, thuật toán tìm kiếm tuyến tính thực hiện các thao tác O[1]

Khóa học Full Stack Web Developer

Trường hợp xấu nhất phức tạp

• Phần tử đang được tìm kiếm có thể ở vị trí cuối cùng trong mảng hoặc hoàn toàn không
• Trong trường hợp đầu tiên, tìm kiếm thành công trong so sánh 'n'
• Trong trường hợp tiếp theo, tìm kiếm không thành công sau khi so sánh 'n'
• Do đó, trong trường hợp xấu nhất, thuật toán tìm kiếm tuyến tính thực hiện phép toán O[n]

Trường hợp phức tạp trung bình

Khi phần tử cần tìm nằm ở giữa mảng, trường hợp trung bình của Thuật toán tìm kiếm tuyến tính là O[n]

Tiếp theo, bạn sẽ tìm hiểu về Độ phức tạp không gian của thuật toán tìm kiếm tuyến tính

Độ phức tạp không gian của thuật toán tìm kiếm tuyến tính

Thuật toán tìm kiếm tuyến tính không chiếm thêm không gian;

Bây giờ bạn đã nắm được mức độ phức tạp của thuật toán tìm kiếm tuyến tính, hãy xem xét một số ứng dụng của nó

Ứng dụng của 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ó các ứng dụng sau

• Tìm kiếm tuyến tính có thể được áp dụng cho cả mảng đơn chiều và đa chiều
• Tìm kiếm tuyến tính dễ thực hiện và hiệu quả khi mảng chỉ chứa một số phần tử.  
• Tìm kiếm tuyến tính cũng hiệu quả khi tìm kiếm được thực hiện để tìm nạp một tìm kiếm trong Danh sách không có thứ tự

Cuối cùng, trong hướng dẫn này, bạn sẽ triển khai thuật toán tìm kiếm tuyến tính bằng mã

cũng đọc. Mảng trong cấu trúc dữ liệu

Thực thi mã của thuật toán tìm kiếm tuyến tính

#include

#include

#include  

int chính []

{

mảng int[50],i,mục tiêu,num;

printf["Bạn muốn mảng có bao nhiêu phần tử"];

scanf["%d",&num];

printf["Nhập các phần tử của mảng. "];

for[i=0;i