Searching Algorithms – Thuật toán tìm kiếm
Thuật toán tìm kiếm được thiết kế để kiểm tra một phần tử hoặc truy xuất một phần tử từ bất kỳ cấu trúc dữ liệu nào mà nó được lưu trữ. Dựa trên loại hoạt động tìm kiếm, các thuật toán này thường được phân loại thành hai loại:
Tìm kiếm tuần tự: Trong đó, danh sách hoặc mảng được duyệt tuần tự và mọi phần tử đều được kiểm tra. Ví dụ: Tìm kiếm tuyến tính .
Tìm kiếm theo khoảng thời gian: Các thuật toán này được thiết kế đặc biệt để tìm kiếm trong cấu trúc dữ liệu được sắp xếp. Loại thuật toán tìm kiếm này hiệu quả hơn nhiều so với Tìm kiếm tuyến tính vì chúng liên tục nhắm mục tiêu vào trung tâm của cấu trúc tìm kiếm và chia đôi không gian tìm kiếm. Ví dụ: Tìm kiếm nhị phân.
1. Tìm kiếm tuyến tính – Linear Search
Cho một mảng arr [] gồm N phần tử, nhiệm vụ là viết một hàm để tìm kiếm một phần tử x đã cho trong arr [].
Ví dụ:
- Đầu vào: arr [] = {10, 20, 80, 30, 60, 50,110, 100, 130, 170}, x = 110;
- Đầu ra: 6
- Giải thích: Phần tử x có ở chỉ số 6
- Đầu vào: arr [] = {10, 20, 80, 30, 60, 50,110, 100, 130, 170}, x = 175;
- Kết quả: -1
- Giải thích: Phần tử x không có trong arr [].
Cách tiếp cận:
Lặp lại từ 0 đến N-1 và so sánh giá trị của mọi chỉ mục với khóa nếu chúng khớp với chỉ mục trả về, nếu vòng lặp kết thúc thì trả về -1 .
Thực hiện theo các bước dưới đây để Triển khai phương pháp trên:
- 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 .
Dưới đây là việc thực hiện phương pháp trên:
- Trong 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;
}
- Trong 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;
}
2. Tìm kiếm nhị phân – Binary Search
Bài toán: Cho một mảng đã sắp xếp arr [] gồm n phần tử, viết hàm tìm kiếm một phần tử x cho trước trong arr [] và trả về chỉ số của x trong mảng.
Coi mảng là 0 chỉ số cơ sở.Ví dụ:
- Đầu vào: arr [] = {10, 20, 30, 50, 60, 80, 110, 130, 140, 170}, x = 110
- Đầu ra: 6
- Giải thích: Phần tử x có mặt ở chỉ số 6.
- Đầu vào: arr [] = {10, 20, 30, 40, 60, 110, 120, 130, 170}, x = 175
- Đầu ra: -1
- Giải thích: Phần tử x không có trong arr [].
Phương pháp tiếp cận tìm kiếm tuyến tính: Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính. Độ phức tạp về thời gian của tìm kiếm Tuyến tính là O (n). Một cách tiếp cận khác để thực hiện tác vụ tương tự là sử dụng Tìm kiếm nhị phân.
Phương pháp tiếp cận tìm kiếm nhị phân:
Tìm kiếm nhị phân là một thuật toán tìm kiếm được sử dụng trong một mảng được sắp xếp bằng cách chia đôi khoảng thời gian tìm kiếm nhiều lần . Ý tưởng của tìm kiếm nhị phân là sử dụng thông tin mà mảng được sắp xếp và giảm độ phức tạp về thời gian thành O (Log n).
Thuật toán tìm kiếm nhị phân: Các bước cơ bản để thực hiện tìm kiếm nhị phân là:
- Bắt đầu với phần tử giữa của toàn mảng làm khóa tìm kiếm.
- Nếu giá trị của khóa tìm kiếm bằng với mục thì trả về một chỉ mục của khóa tìm kiếm.
- Hoặc nếu giá trị của khóa tìm kiếm nhỏ hơn mục ở giữa khoảng, hãy thu hẹp khoảng xuống nửa dưới.
- Nếu không, hãy thu hẹp nó xuống nửa trên.
- Lặp lại kiểm tra từ điểm thứ hai cho đến khi giá trị được tìm thấy hoặc khoảng thời gian trống.
Thuật toán tìm kiếm nhị phân có thể được thực hiện theo hai cách sau
– Phương pháp lặp lại:
binarySearch (arr, x, low, high)
lặp lại cho đến low = high
mid = (low + high) / 2
if (x == arr [mid])
return mid
else if (x> arr [mid]) // x is ở bên phải
low = mid + 1
else // x ở bên trái
high = mid - 1– Phương pháp đệ quy:
binarySearch (arr, x, low, high)
if low> high
return False
else
mid = (low + high) / 2
if x == arr [mid]
return mid
else if x> arr [mid] // x nằm trên bên phải
trả về binarySearch (arr, x, mid + 1, high)
else // x ở bên phải
trả về binarySearch (arr, x, low, mid - 1)Thuật toán tìm kiếm nhị phân từng bước: Về cơ bản, chúng tôi bỏ qua một nửa số phần tử chỉ sau một lần so sánh.
- So sánh x với phần tử ở giữa.
- Nếu x khớp với phần tử ở giữa, chúng ta trả về chỉ số giữa.
- Khác Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa mảng con bên phải sau phần tử giữa. Vì vậy, chúng tôi tái diễn cho một nửa bên phải.
- Khác (x nhỏ hơn) lặp lại cho nửa bên trái.
Triển khai đệ quy Tìm kiếm nhị phân:
– Trong C++
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
– Trong C
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
3. Tìm kiếm bậc ba – Ternary Search
Tìm kiếm bậc ba là một thuật toán giảm (theo hằng số) và chinh phục có thể được sử dụng để tìm một phần tử trong một mảng . Nó tương tự như tìm kiếm nhị phân trong đó chúng ta chia mảng thành hai phần nhưng trong thuật toán này, chúng ta chia mảng đã cho thành ba phần và xác định mảng có khóa (phần tử được tìm kiếm). Chúng ta có thể chia mảng thành ba phần bằng cách lấy mid1 và mid2 có thể được tính như hình dưới đây. Ban đầu, l và r sẽ lần lượt bằng 0 và n-1, trong đó n là độ dài của mảng.
Nó cũng giống như tìm kiếm nhị phân. Sự khác biệt duy nhất là, nó làm giảm thời gian phức tạp hơn một chút. Độ phức tạp thời gian của nó là O (log n cơ số 3) và độ phức tạp của tìm kiếm nhị phân là O (log n cơ số 2).
mid1 = l + (rl) / 3
mid2 = r – (rl) / 3
Lưu ý: Mảng cần được sắp xếp để thực hiện tìm kiếm bậc ba trên đó.
Các bước để thực hiện Tìm kiếm Thứ ba:
- Đầu tiên, chúng tôi so sánh khóa với phần tử ở mid1. Nếu tìm thấy bằng nhau, chúng tôi trả về mid1.
- Nếu không, thì chúng ta so sánh khóa với phần tử ở mid2. Nếu tìm thấy bằng nhau, chúng tôi trả về mid2.
- Nếu không, thì chúng tôi kiểm tra xem khóa có nhỏ hơn phần tử ở mid1 hay không. Nếu có, sau đó lặp lại phần đầu tiên.
- Nếu không, thì chúng ta kiểm tra xem khóa có lớn hơn phần tử ở giữa 2 hay không. Nếu có, sau đó tái diễn sang phần thứ ba.
- Nếu không, sau đó chúng tôi tái diễn phần thứ hai (giữa).
Triển khai đệ quy Tìm kiếm bậc ba
– Trong C++
#include <bits/stdc++.h>
using namespace std;
int ternarySearch(int l, int r, int key, int ar[])
{
if (r >= l) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
if (key < ar[mid1]) {
return ternarySearch(l, mid1 - 1, key, ar);
}
else if (key > ar[mid2]) {
return ternarySearch(mid2 + 1, r, key, ar);
}
else {
return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
}
}
return -1;
}
int main()
{
int l, r, p, key;
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
l = 0;
r = 9;
key = 5;
p = ternarySearch(l, r, key, ar);
cout << "Index of " << key
<< " is " << p << endl;
key = 50;
p = ternarySearch(l, r, key, ar);
cout << "Index of " << key
<< " is " << p << endl;
}
– Trong C
#include <stdio.h>
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
if (r >= l) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
if (key < ar[mid1]) {
return ternarySearch(l, mid1 - 1, key, ar);
}
else if (key > ar[mid2]) {
return ternarySearch(mid2 + 1, r, key, ar);
}
else {
return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
}
}
return -1;
}
int main()
{
int l, r, p, key;
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
l = 0;
r = 9;
key = 5;
p = ternarySearch(l, r, key, ar);
printf("Index of %d is %d\n", key, p);
key = 50;
p = ternarySearch(l, r, key, ar);
printf("Index of %d is %d", key, p);
}
Độ phức tạp về thời gian của tìm kiếm nhị phân nhiều hơn tìm kiếm bậc ba nhưng không có nghĩa là tìm kiếm bậc ba tốt hơn. Trên thực tế, số lượng phép so sánh trong tìm kiếm bậc ba nhiều hơn khiến nó chậm hơn so với tìm kiếm nhị phân.