🔥CHỌN LỌC TOP NHỮNG KHOÁ HỌC LẬP TRÌNH ONLINE NHIỀU NGƯỜI THEO HOC TẠI ĐÂY🔥

Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Linear Search, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Linear Search thông qua các phần sau.

1. Giới thiệu

Bài toán: Cho một mảng arr [] gồm n phần tử, hãy viết hàm tìm kiếm một phần tử x cho trước trong arr [].

Ví dụ:

Đầu vào: arr [] = {10, 20, 80, 30, 60, 50,

110, 100, 130, 170}

x = 110;

Đầu ra: 6

Nguyên tố x hiện diện ở chỉ số 6

Đầu vào: arr [] = {10, 20, 80, 30, 60, 50,

110, 100, 130, 170}

x = 175;

Đầu ra: -1

Phần tử x không có trong arr [].

Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính(Linear Search), tức là

  • Bắt đầu từ phần tử ngoài cùng bên trái của arr [] và lần lượt so sánh x với từng phần tử của arr []
  • Nếu x khớp với một phần tử, trả về chỉ mục.
  • Nếu x không khớp với bất kỳ phần tử nào, trả về -1.

2. Code ví dụ trên nhiều ngôn ngữ khác

C++


// C++ code to linearly search x in arr[]. If x 
// is present then return its location, otherwise 
// return -1 
  
#include <iostream> 
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 " <<result; 
   return 0; 
}

C


// C code to linearly search x in arr[]. If x 
// is present then return its location, otherwise 
// return -1 
  
#include <stdio.h> 
  
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; 
}

Java


// Java code for linearly searching x in arr[]. If x  
// is present then return its location, otherwise  
// return -1  
  
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); 
} 
}

Python3


# Python3 code to linearly search x in arr[].  
# If x is present then return its location, 
# otherwise return -1 
  
def search(arr, n, x): 
  
    for i in range (0, n): 
        if (arr[i] == x): 
            return i; 
    return -1; 
  
# Driver Code 
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);

C#

// C# code to linearly search x in arr[]. If x  
// is present then return its location, otherwise  
// return -1  
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); 
    } 
}

PHP


<?php 
// PHP code for linearly search x in arr[].  
// If x is present then return its location,  
// otherwise return -1  
  
function search($arr, $x) 
{ 
    $n = sizeof($arr); 
    for($i = 0; $i < $n; $i++) 
    { 
        if($arr[$i] == $x) 
            return $i; 
    } 
    return -1; 
} 
  
// Driver Code 
$arr = array(2, 3, 4, 10, 40);  
$x = 10; 
      
$result = search($arr, $x); 
if($result == -1) 
    echo "Element is not present in array"; 
else
    echo "Element is present at index " , 
                                 $result; 
?>

Kết quả

Element is present at index 3

3. Độ phức tạp

Độ phức tạp thời gian của thuật toán trên là O (n).

Tìm kiếm tuyến tính(Linear Search) hiếm khi được sử dụng thực tế vì các thuật toán tìm kiếm khác như thuật toán tìm kiếm nhị phân(binary search) và bảng băm(hash tables) cho phép so sánh tìm kiếm nhanh hơn đáng kể so với tìm kiếm tuyến tính.

Nguồn và Tài liệu tiếng anh tham khảo:

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

Chào thân ái và quyết thắng!

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!

BÀI VIẾT LIÊN QUANXEM THÊM