Bài tập

Thuật toán tìm kiếm tuyến tính (Tìm kiếm tuần tự): Một cách đơn giản để tìm kiếm

avatar
Huy Erick
00:00 12/04/2024

Thuật toán 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ự, là phương pháp tìm kiếm một phần tử trong danh sách bằng cách duyệt lần lượt từng phần tử...

Thuật toán 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ự, là phương pháp tìm kiếm một phần tử trong danh sách bằng cách duyệt lần lượt từng phần tử của danh sách cho đến khi tìm thấy giá trị mong muốn hoặc đã duyệt qua toàn bộ danh sách.

Tìm kiếm tuyến tính: Đơn giản và hiệu quả

Thuật toán tìm kiếm tuyến tính rất đơn giản khi được thực hiện. Nó rất hiệu quả khi tìm kiếm trên một danh sách nhỏ hoặc một danh sách chưa được sắp xếp đơn giản. Trong trường hợp cần tìm kiếm nhiều lần, dữ liệu thường được xử lý trước khi tìm kiếm, có thể sắp xếp hoặc xây dựng theo cấu trúc dữ liệu đặc trưng để tăng hiệu suất tìm kiếm.

Phân loại:

Xem thêm:
  • Giải thuật tìm kiếm tuyến tính thuộc cấu trúc dữ liệu danh sách.
  • Độ phức tạp thời gian: O(n) khi phần tử tìm kiếm nằm ở cuối danh sách hoặc không có trong danh sách.
  • Thời gian chạy tốt nhất: O(1) khi phần tử cần tìm nằm ngay đầu danh sách.
  • Độ phức tạp không gian: O(n)

Bài toán: Cho một mảng gồm n phần tử, hãy viết hàm để tìm kiếm một phần tử x đã cho trong mảng.

Thuật toán tìm kiếm tuyến tính (Tìm kiếm tuần tự)

Ví dụ:

  • Đầu vào: mảng A[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170}, x = 110

  • Đầu ra: Phần tử x có mặt ở vị trí số 6

  • Đầu vào: mảng A[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170}, x = 175

  • Đầu ra: Phần tử x không có trong mảng A[].

Mã giả

Phiên bản lặp tự nhiên

Đây là phiên bản phổ biến của thuật toán tìm kiếm tuần tự, kết quả trả về sẽ là vị trí của phần tử cần tìm hoặc một giá trị Δ thể hiện việc không tìm thấy phần tử trong danh sách.

  1. Duyệt qua từng phần tử trong danh sách:
    1. Nếu phần tử đó có giá trị mong muốn, dừng tìm kiếm và trả về vị trí của phần tử.
  2. Trả về giá trị Δ.

Nếu danh sách được lưu trữ dưới dạng mảng, vị trí của phần tử cần tìm có thể là chỉ số của nó trong mảng, còn giá trị Δ có thể là chỉ số nằm trước phần tử đầu tiên (0 hoặc -1 tùy vào danh sách).

Nếu danh sách là một danh sách liên kết, vị trí của phần tử được trả về có thể là địa chỉ của nó, còn giá trị Δ có thể là giá trị null.

Phiên bản đệ quy

Đây là phiên bản đệ quy khi thực hiện thuật toán tìm kiếm tuần tự.

  1. Nếu danh sách rỗng, trả về giá trị Λ.
  2. Ngược lại:
    1. Nếu phần tử đầu tiên của danh sách có giá trị mong muốn, trả về vị trí của nó.
    2. Ngược lại, tìm kiếm giá trị trong phần còn lại của danh sách và trả về kết quả.

Sử dụng phần tử cầm canh

Một phương pháp được sử dụng để cải thiện hiệu suất của thuật toán là chèn phần tử muốn tìm kiếm và cuối danh sách như một phần tử cầm canh (sentinel).

  1. Gán A[n + 1] bằng giá trị x.
  2. Gán i bằng 1.
  3. Lặp lại quá trình sau:
    1. Nếu A[i] = x, thoát khỏi vòng lặp.
    2. Gán i = i + 1.
  4. Trả về giá trị i.

Việc thêm phần tử cầm canh giúp giảm số lần so sánh chỉ số hiện tại i với số phần tử n trong mỗi vòng lặp. Tuy nhiên, điều này chỉ có thể áp dụng khi vị trí cuối cùng của danh sách tồn tại và chưa được sử dụng.

Viết thuật toán tìm kiếm tuyến tính với ngôn ngữ lập trình C, C++, Java, Python3, PHP, C

Tìm kiếm tuyến tính với C++

#include 
using namespace std;

int search(int arr[], int n, int x) {
  int i;
  for (i = 0; i  n; i++)
    if (arr[i] == x)
      return i;
  return -1;
}

int main(void) {
  int arr[] = { 2, 3, 4, 10, 40 };
  int x = 10;
  int n = sizeof(arr) / sizeof(arr[0]);
  int result = search(arr, n, x);
  (result == -1)? cout"Element is not present in array" : cout"Element is present at index "

Tìm kiếm tuyến tính với C

#include 

int search(int arr[], int n, int x) {
  int i;
  for (i = 0; i  n; i++)
    if (arr[i] == x)
      return i;
  return -1;
}

int main(void) {
  int arr[] = { 2, 3, 4, 10, 40 };
  int x = 10;
  int n = sizeof(arr) / sizeof(arr[0]);
  int result = search(arr, n, x);
  (result == -1) ? printf("Element is not present in array") : printf("Element is present at index %d", result);
  return 0;
}

Tìm kiếm tuyến tính với Python3

def search(arr, n, x):
  for i in range (0, n):
    if (arr[i] == x):
      return i;
  return -1;

arr = [2, 3, 4, 10, 40]
x = 10
n = len(arr)
result = search(arr, n, x)
if result == -1:
  print("Element is not present in array")
else:
  print("Element is present at index", result)

Tìm kiếm tuyến tính với Java

class GFG {
  public static int search(int arr[], int x) {
    int n = arr.length;
    for(int i = 0; i  n; i++) {
      if(arr[i] == x)
        return i;
    }
    return -1;
  }

  public static void main(String args[]) {
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int result = search(arr, x);
    if(result == -1)
      System.out.print("Element is not present in array");
    else
      System.out.print("Element is present at index " + result);
  }
}

Tìm kiếm tuyến tính với PHP

Tìm kiếm tuyến tính với C

using System;

class GFG {
  public static int search(int[] arr, int x) {
    int n = arr.Length;
    for(int i = 0; i  n; i++) {
      if(arr[i] == x)
        return i;
    }
    return -1;
  }

  public static void Main() {
    int[] arr = { 2, 3, 4, 10, 40 };
    int x = 10;
    int result = search(arr, x);
    if(result == -1)
      Console.WriteLine("Element is not present in array");
    else
      Console.WriteLine("Element is present at index " + result);
  }
}

Chạy thử và xem kết quả: Element is present at index 3

BÀI LIÊN QUAN
1