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

Thuật toán tìm kiếm tuyến tính (linear search) hay có cách gọi khác là thuật toán tìm kiếm tuần tự (Sequential search)  là một cách thức tìm kiếm một phần tử cho trước trong một mục lục bằng cách duyệt lần lượt từng phần tử của mục lục đó cho đến lúc tìm thấy giá trị mong chờ hay đã duyệt qua toàn thể mục lục.

Tìm kiếm tuyến tính là một giải thuật rất dễ khi hiện thực. Giải thuật này tỏ ra khá hiệu quả khi cần tìm kiếm trên một mục lục đủ nhỏ hoặc một mục lục chưa sắp thứ tự dễ dàng. Trong trường hợp cần tìm kiếm nhiều lần, dữ liệu thường được giải quyết một lần trước khi tìm kiếm: có thể được xếp đặt theo thứ tự, hoặc được xây dựng theo một kết cấu dữ liệu đặc thù cho giải thuật hiệu quả hơn,…

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

Chẳng hạn:

Đầu vào: mảng ?[] = {10, 20, 80, 30, 60, 50, 
                     110, 100, 130, 170}
          Ҳ = 110;
Đầu ra: 6
Phần tử Ҳ có mặt ở địa điểm số 6

Đầu vào: mảng ?[] = {10, 20, 80, 30, 60, 50, 
                     110, 100, 130, 170}
           Ҳ = 175;
Đầu ra: -1
Phần tử Ҳ không có trong mảng ?[].

Mã giả

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

Đây là phiên bản hay gặp nhất của giải thuật này, kết quả trả về sẽ là địa điểm của phần tử cần tìm hoặc một giá trị Δ trổ tài việc không tìm thấy phần tử trong mục lục đó.

 1. For each item in the danh sách:
     1. if that item has the desired value,
         1. stop the search and return the item's location.
 2. Return 'Δ'

Nếu mục lục được lưu trữ dưới dạng mảng, địa điểm 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 tien (0 hoặc -1 tùy theo mục lục).

Nếu mục lục là một mục lục link, địa điểm của phần tử được trả về có thể nằm dưới dạng địa chỉ của no, còn giá trị Δ có thể là giá trị null.

Phiên bản đệ quy

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

 1. if the danh sách is empty, return Λ;
 2. else
    1. if the first item of the danh sách has the desired value
       1. return its location;
    2. else 
       1. search the value in the remainder of the danh sách, and return the result.

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

Một cách thức được sử dụng để cải tổ hiệu quả của giải thuật là chèn phần tử mong muốn tìm kiếm & cuối mục lục như một phần tử cầm canh () như được trình bày dưới đây:

 1. Set ?[n + 1] to Ҳ. 
 2. Set ι to 1.
 3. Repeat this loop:
     1. If ?[i] = Ҳ, 
        1. exit the loop.
     2. Set ι to ι + 1.
 4. Return ι.

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

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

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

#include <iostreamvàgt; 
using namespace std; 
  
int search(int arr[], int и, int Ҳ) 
{ 
    int ι; 
    for (ι = 0; ι < и; ι++) 
        if (arr[i] == Ҳ) 
            return ι; 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int Ҳ = 10; 
    int и = sizeof(arr) / sizeof(arr[0]); 
    int result = search(arr, и, Ҳ); 
   (result == -1)? coutvàlt;<"Element is not present in array" 
                 : coutvàlt;<"Element is present at index " <<result; 
   return 0; 
}

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

#include <stdio.hvàgt; 
  
int search(int arr[], int и, int Ҳ) 
{ 
    int ι; 
    for (ι = 0; ι < и; ι++) 
        if (arr[i] == Ҳ) 
            return ι; 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int Ҳ = 10; 
    int и = sizeof(arr) / sizeof(arr[0]); 
    int result = search(arr, и, Ҳ); 
    (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, и, Ҳ): 
  
    for ι in range (0, и): 
        if (arr[i] == Ҳ): 
            return ι; 
    return -1; 
  
# Driver Code 
arr = [ 2, 3, 4, 10, 40 ]; 
Ҳ = 10; 
и = len(arr); 
result = search(arr, и, Ҳ) 
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 Ҳ) 
{ 
    int и = arr.length; 
    for(int ι = 0; ι < и; ι++) 
    { 
        if(arr[i] == Ҳ) 
            return ι; 
    } 
    return -1; 
} 
  
public static void main(String args[]) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 };  
    int Ҳ = 10; 
      
    int result = search(arr, Ҳ); 
    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:

<?php 
  
function search($arr, $Ҳ) 
{ 
    $и = sizeof($arr); 
    for($ι = 0; $ι < $и; $ι++) 
    { 
        if($arr[$i] == $Ҳ) 
            return $ι; 
    } 
    return -1; 
} 
  
// Driver Code 
$arr = array(2, 3, 4, 10, 40);  
$Ҳ = 10; 
      
$result = search($arr, $Ҳ); 
if($result == -1) 
    echo "Element is not present in array"; 
else
    echo "Element is present at index " , 
                                 $result; 
?>

Tìm kiếm tuyến tính với ₵#:

using System;  
  
class GFG  
{  
    public static int search(int[] arr, int Ҳ) 
    { 
        int и = arr.Length; 
        for(int ι = 0; ι < и; ι++) 
        { 
            if(arr[i] == Ҳ) 
                return ι; 
        } 
        return -1; 
    } 
      
    public static void Main() 
    { 
        int[] arr = { 2, 3, 4, 10, 40 };  
        int Ҳ = 10; 
          
        int result = search(arr, Ҳ); 
        if(result == -1) 
            Console.WriteLine("Element is not present in array"); 
        else
            Console.WriteLine("Element is present at index "+ result); 
    } 
}

Chạy thử & xem kết quả:

Element is present at index 3
Xem Thêm  SQL FOREIGN KEY (Với các ví dụ) - sql chọn khóa ngoại

Viết một bình luận