Hướng dẫn how does linear search work in python? - tìm kiếm tuyến tính hoạt động như thế nào trong python?

Trong hướng dẫn này, bạn sẽ tìm hiểu về tìm kiếm tuyến tính. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của tìm kiếm tuyến tính C, C ++, Java và Python.

Tìm kiếm tuyến tính là một thuật toán tìm kiếm tuần tự nơi chúng tôi bắt đầu từ một đầu và kiểm tra mọi yếu tố của danh sách cho đến khi tìm thấy phần tử mong muốn. Nó là thuật toán tìm kiếm đơn giản nhất.

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

Các bước sau đây được theo dõi để tìm kiếm một phần tử k = 1 trong danh sách bên dưới.

1. Bắt đầu từ phần tử đầu tiên, so sánh k với mỗi phần tử x. So sánh với từng phần tử
   Compare with each element
2. Nếu x == k, trả lại chỉ mục. Yếu tố tìm thấy
   Element found
3. Khác, không tìm thấy trở lại.

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

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

Ví dụ về Python, Java và C/C ++

# Linear Search in Python


def linearSearch(array, n, x):

    # Going through array sequencially
    for i in range(0, n):
        if (array[i] == x):
            return i
    return -1


array = [2, 4, 0, 1, 9]
x = 1
n = len(array)
result = linearSearch(array, n, x)
if(result == -1):
    print("Element not found")
else:
    print("Element found at index: ", result)

// Linear Search in Java

class LinearSearch {
  public static int linearSearch(int array[], int x) {
  int n = array.length;

  // Going through array sequencially
  for (int i = 0; i < n; i++) {
    if (array[i] == x)
    return i;
  }
  return -1;
  }

  public static void main(String args[]) {
  int array[] = { 2, 4, 0, 1, 9 };
  int x = 1;

  int result = linearSearch(array, x);

  if (result == -1)
    System.out.print("Element not found");
  else
    System.out.print("Element found at index: " + result);
  }
}

// Linear Search in C

#include 

int search(int array[], int n, int x) {
  
  // Going through array sequencially
  for (int i = 0; i < n; i++)
    if (array[i] == x)
      return i;
  return -1;
}

int main() {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

  int result = search(array, n, x);

  (result == -1) ? printf("Element not found") : printf("Element found at index: %d", result);
}

// Linear Search in C++

#include 
using namespace std;

int search(int array[], int n, int x) {

  // Going through array sequencially
  for (int i = 0; i < n; i++)
    if (array[i] == x)
      return i;
  return -1;
}

int main() {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

  int result = search(array, n, x);

  (result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result;
}

Sự phức tạp tìm kiếm tuyến tính

Độ phức tạp về thời gian: O (n) O(n)

Độ phức tạp không gian: O(1) O(1)

Ứng dụng tìm kiếm tuyến tính

1. Để tìm kiếm các hoạt động trong các mảng nhỏ hơn (

Python là một trong những ngôn ngữ phổ biến và mạnh mẽ nhất. Phải mất một vài dòng để thực thi mã, điều này làm cho nó nhiều ngôn ngữ thân thiện với người dùng. Trong hướng dẫn này, chúng tôi sẽ tìm hiểu tìm kiếm tuyến tính trong Python. Tìm kiếm là một kỹ thuật để tìm ra phần tử cụ thể có mặt hoặc không trong danh sách đã cho.

Có hai loại tìm kiếm -

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

Cả hai kỹ thuật đều được sử dụng rộng rãi để tìm kiếm một yếu tố trong danh sách đã cho.

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

Tìm kiếm tuyến tính là một phương pháp tìm các yếu tố trong danh sách. Nó cũng được gọi là một tìm kiếm tuần tự. & nbsp; Đây là thuật toán tìm kiếm đơn giản nhất vì nó tìm kiếm phần tử mong muốn theo cách tuần tự.

Nó so sánh từng yếu tố với giá trị mà chúng tôi đang tìm kiếm. Nếu cả hai đều được 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.

Khái niệm tìm kiếm tuyến tính

Hãy hiểu các bước sau để tìm khóa phần tử = 7 trong danh sách đã cho.

Bước - 1: Bắt đầu tìm kiếm từ phần tử đầu tiên và phím kiểm tra = 7 với mỗi phần tử của danh sách x. Start the search from the first element and Check key = 7 with each element of list x.

Bước - 2: Nếu tìm thấy phần tử, hãy trả về vị trí chỉ mục của khóa. If element is found, return the index position of the key.

Bước - 3: Nếu không tìm thấy phần tử, phần tử trở lại không có mặt. If element is not found, return element is not present.

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

Có danh sách n phần tử và giá trị khóa sẽ được tìm kiếm.

Dưới đây là thuật toán tìm kiếm tuyến tính.

Chương trình Python

Hãy hiểu việc triển khai Python sau đây của thuật toán tìm kiếm tuyến tính.

Chương trình

Output:

Element found at index:  4

Explanation:

Trong mã trên, chúng tôi đã tạo một hàm linear_search (), có ba đối số - list1, độ dài của danh sách và số để tìm kiếm. Chúng tôi đã xác định cho vòng lặp và lặp từng phần tử và so sánh với giá trị khóa. Nếu phần tử được tìm thấy, hãy trả về chỉ số khác trả về -1, có nghĩa là phần tử không có trong danh sách.linear_Search(), which takes three arguments - list1, length of the list, and number to search. We defined for loop and iterate each element and compare to the key value. If element is found, return the index else return -1 which means element is not present in the list.

Độ phức tạp tìm kiếm tuyến tính

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

• Trường hợp cơ sở - O (1)
• Trường hợp trung bình - O (n)
• Trường hợp xấu nhất -o (n)

Thuật toán tìm kiếm tuyến tính phù hợp cho danh sách nhỏ hơn (

Để có được kết quả nhanh, chúng ta có thể sử dụng thuật toán tìm kiếm nhị phân.

Chúng tôi đã thảo luận về khái niệm cơ bản của tìm kiếm tuyến tính. Trong hướng dẫn tiếp theo, chúng tôi sẽ tìm hiểu thuật toán tìm kiếm thứ hai và phổ biến nhất có tên là tìm kiếm nhị phân.

Làm thế nào để Python thực hiện tìm kiếm tuyến tính?

Làm thế nào để một tìm kiếm tuyến tính hoạt động?

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

Làm thế nào để bạn thực hiện tìm kiếm tuyến tính tìm kiếm?