Thuật Toán Tìm Kiếm Tuyến Tính (Tìm Kiếm Tuần Tự) - DNMTechs

Thuật toán tìm kiếm tuyến tính (linear search) hay còn gọi là thuật toán tìm kiếm tuần tự (Sequential search)  là một phương pháp tìm kiếm một phần tử cho trước trong một 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 lúc tìm thấy giá trị mong muốn hay đã duyệt qua toàn bộ danh sách.

Tìm kiếm tuyến tính là một giải thuật rất đơn giản 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 danh sách đủ nhỏ hoặc một danh sách chưa sắp thứ tự đơ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ý một lần trước khi tìm kiếm: có thể được sắp xếp theo thứ tự, hoặc được xây dựng theo một cấu trúc dữ liệu đặc trưng cho giải thuật hiệu quả hơn,…

Phân loại	giải thuật tìm kiếm
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 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 [].

Ví dụ:

Đầu vào: mảng A[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 110; Đầu ra: 6 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: -1 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 hay gặp nhất của giải thuật này, 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. For each item in the list: 1. if that item has the desired value, 1. stop the search and return the item's location. 2. Return 'Δ'

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 tien (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ể 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 list is empty, return Λ; 2. else 1. if the first item of the list has the desired value 1. return its location; 2. else 1. search the value in the remainder of the list, and return the result.

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 quả của giải thuật 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) như được trình bày dưới đây:

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

Việc thêm phần tử cầm canh giúp giảm bớt việc so sánh chỉ số hiện tại i với số các phần tử n ở mỗi vòng lặp. Tuy nhiên, điều này chỉ có thể được sử dụng khi vị trí cuối cùng của danh sách 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 ngữ lập trình C, C++, Java, Python3

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

#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; }

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

#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; }

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; # 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);

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:

<?php 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; ?>

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