Tìm kiếm tuyến tính: Python, C++ Ví dụ
Sarah Chen
Thuật toán tìm kiếm là gì?
Thuật toán tìm kiếm được thiết kế để tìm một phần tử hoặc đối tượng từ một tập hợp các phần tử hoặc đối tượng có cấu trúc dữ liệu nhất định. Ví dụ, tìm kiếm chiều cao tối thiểu từ một danh sách chiều cao nhất định hoặc tìm kiếm điểm cao nhất từ một danh sách hoặc mảng số. Một số thuật toán tìm kiếm phổ biến bao gồm "Tìm kiếm tuyến tính", "Tìm kiếm nhị phân", "Tìm kiếm nhảy", "Tìm kiếm Fibonacci", v.v.
Tìm kiếm tuyến tính là gì?
Tìm kiếm tuyến tính là một trong những thuật toán tìm kiếm đơn giản nhất. Từ một danh sách hoặc mảng nhất định, nó tìm kiếm từng phần tử đã cho. Tìm kiếm tuyến tính lặp lại toàn bộ danh sách và kiểm tra xem có phần tử cụ thể nào bằng phần tử tìm kiếm hay không. Nó còn được gọi là tìm kiếm tuần tự.
Chức năng tìm kiếm tuyến tính làm gì?
Một mảng các số nguyên được cho là “Numbers,” và biến “item” chứa số nguyên cần tìm kiếm.
Bây giờ, thuật toán Tìm kiếm tuyến tính có thể cung cấp kết quả sau:
- “-1”; điều này có nghĩa là phần tử đã cho không được tìm thấy trong mảng
- Bất kỳ số nào từ 0 đến n-1; có nghĩa là phần tử tìm kiếm được tìm thấy và nó trả về chỉ mục của phần tử trên mảng. Ở đây, “n” đại diện cho kích thước của mảng.
Tìm kiếm tuyến tính hoạt động như thế nào?
Giả sử một mảng chứa các số nguyên. Nhiệm vụ là tìm một số cho trước trong mảng.
- Nếu số nằm trong mảng thì chúng ta cần trả về chỉ số của số đó.
- Nếu không tìm thấy số đã cho thì nó sẽ trả về -1.
Trong sơ đồ, “Dữ liệu” là mảng số nguyên, “N” là kích thước của mảng và “item” là số chúng ta muốn tìm kiếm trong mảng.
Lưu đồ cho thuật toán tìm kiếm tuyến tính:
Dưới đây là các bước của sơ đồ:
Bước 1) Đọc mục tìm kiếm, “item”.
Bước 2) Bắt đầu i=0 và chỉ mục=-1
Bước 3) Nếu tôi
Bước 4) Nếu Data[i] bằng “item” thì chuyển sang bước 5. Nếu không thì chuyển sang bước 6.
Bước 5) Index = i (Vì mục này được tìm thấy ở chỉ mục số i). Chuyển sang bước 8.
Bước 6) tôi = tôi +1.
Bước 7) Chuyển sang bước 3.
Bước 8) Dừng lại.
Để đơn giản, chúng tôi cung cấp một ví dụ với một mảng các số nguyên. Tìm kiếm tuyến tính cũng có thể áp dụng được trong chuỗi, mảng đối tượng hoặc cấu trúc.
Biệt danh Code cho thuật toán tìm kiếm tuần tự
function linearSearch: in →Data[], item foundAt = -1 for i in (0 to data.length): if data[i] equals item // item is found in the array // returning the index return i // item not found in the array // -1 means no item found, as negative index is not valid return -1
C++ Code Ví dụ tìm kiếm tuyến tính
#include < bits / stdc++.h >
using namespace std;
int linearSearch(int * arr, int item, int n) {
int idx = -1;
for (int i = 0; i < n; i++) {
if (arr[i] == item) {
idx = i;
break;
}
}
return idx;
}
int main() {
int array[] = {
1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
};
int n = sizeof(array) / sizeof(arr[0]);
int item;
cout << "Enter a number to search: ";
cin >> item;
int idx = linearSearch(arr, item, n);
if (idx >= 0) {
cout << item << " is found at index " << idx << endl;
} else {
cout << "Could not find " << item << " in the array" << endl;
}
}
Đầu ra:
Enter a number to search: -10 -10 is found at index 14
Python Code Ví dụ tìm kiếm tuyến tính
def linearSearch(data, item):
for i in range(len(data)):
if data[i] == item:
return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
print("{} is found at index {}".format(item, idx))
else :
print("{} was not found".format(item))
Đầu ra:
Enter a number to search: -10 -10 is found at index 14
Phân tích độ phức tạp của thuật toán tìm kiếm tuyến tính
Nói chung, độ phức tạp về thời gian có nghĩa là lượng thời gian CPU để thực hiện một tác vụ nhất định. Trong thuật toán tìm kiếm tuyến tính, nhiệm vụ là tìm khóa tìm kiếm từ phần tử của mảng.
Có ba loại độ phức tạp về thời gian:
- Trường hợp xấu nhất
- Kịch bản hay nhất
- Tình huống trường hợp trung bình
Độ phức tạp thời gian của tìm kiếm tuyến tính trong trường hợp xấu nhất:
Giả sử chúng ta cần thực hiện tìm kiếm tuyến tính trong một mảng có kích thước là “n”. Chúng ta có thể tìm thấy mục tìm kiếm trong khoảng từ 0 đến n-1. Trong trường hợp xấu nhất, thuật toán sẽ cố gắng khớp tất cả các phần tử trong mảng với phần tử tìm kiếm.
Trong trường hợp đó, độ phức tạp trường hợp xấu nhất sẽ là O(n). Ở đây, “O”-big O Notation có nghĩa là hàm độ phức tạp.
Độ phức tạp thời gian của tìm kiếm tuyến tính trong Kịch bản tốt nhất:
Giả sử chúng ta đang tìm kiếm một phần tử nằm ở vị trí đầu tiên trong mảng. Trong trường hợp này, thuật toán tìm kiếm tuyến tính sẽ không tìm kiếm tất cả n phần tử trong mảng. Do đó, độ phức tạp sẽ là O(1). Điều này có nghĩa là thời gian không đổi.
Độ phức tạp thời gian của tìm kiếm tuyến tính trong trường hợp trung bình:
Khi tìm thấy một phần tử ở chỉ số giữa của mảng, thì có thể nói rằng độ phức tạp trường hợp trung bình cho tìm kiếm tuyến tính là O(N), trong đó N là độ dài của mảng.
Độ phức tạp không gian của thuật toán tìm kiếm tuyến tính
Độ phức tạp về không gian cho tìm kiếm tuyến tính luôn là O(N) vì chúng ta không cần lưu trữ hoặc sử dụng bất kỳ loại biến tạm thời nào trong hàm tìm kiếm tuyến tính.
Cách cải thiện thuật toán tìm kiếm tuyến tính
Có thể thực hiện tìm kiếm nhiều lần trong suốt vòng đời của chương trình. Cũng có thể chúng ta đang chạy thuật toán tìm kiếm tuyến tính và tìm kiếm bất kỳ khóa cụ thể nào nhiều lần. Chúng ta có thể sử dụng “Thuật toán tìm kiếm nhị phân” nếu mảng là mảng được sắp xếp.
Giả sử mảng bao gồm 10 nghìn số và phần tử đích được tìm thấy ở chỉ mục thứ 5000. Vì vậy, thuật toán sẽ cố gắng so sánh 5000 phần tử. Bây giờ, so sánh là những nhiệm vụ nặng về CPU. Để tối ưu hóa thuật toán tìm kiếm tuyến tính, chúng ta có hai lựa chọn.
- Chuyển vị
- Di chuyển về phía trước
Chuyển vị:
Trong phương pháp này, chúng ta sẽ hoán đổi phần tử tìm kiếm với phần tử trước đó trong mảng. Ví dụ, giả sử bạn có một mảng như sau:
Dữ liệu[] = {1,5,9,8,7,3,4,11}
Bây giờ chúng ta muốn tìm kiếm 4. Các bước chuyển vị:
Bước 1) “4” được tìm thấy ở chỉ số 6. Phải mất sáu lần so sánh.
Bước 2) Hoán đổi dữ liệu[6] và dữ liệu[5]. Khi đó mảng dữ liệu sẽ có dạng:
Dữ liệu[] = {1,5,9,8,7,4,3,11}
Bước 3) Tìm kiếm lại 4. Tìm thấy ở chỉ số 5. Lần này phải mất XNUMX lần so sánh.
Bước 4) Hoán đổi dữ liệu [5] và dữ liệu [4]. Khi đó mảng dữ liệu sẽ trông như thế này:
Dữ liệu [] = {1,5,9,8,4,7,3,11}
Bây giờ, nếu bạn để ý, một khóa càng được tìm kiếm thường xuyên thì chỉ mục càng giảm. Do đó, giảm số lượng so sánh.
Di chuyển về phía trước:
Trong phương pháp này, chúng tôi hoán đổi phần tử tìm kiếm ở chỉ mục thứ 0. Bởi vì nếu tìm lại, chúng ta có thể tìm thấy nó ở thời điểm O(1).
Ứng dụng thuật toán tìm kiếm tuyến tính
Dưới đây là một số ứng dụng tìm kiếm tuyến tính chúng ta có thể sử dụng.
- Đối với các mảng có kích thước nhỏ hoặc chỉ một vài phần tử trong danh sách, việc sử dụng tìm kiếm tuyến tính sẽ dễ dàng hơn.
- Phương pháp tìm kiếm tuyến tính có thể được sử dụng đơn lẻ hoặc mảng đa chiều hoặc các cấu trúc dữ liệu khác.
- Nói chung, tìm kiếm tuyến tính rất đơn giản và hiệu quả để thực hiện tìm kiếm trong dữ liệu “không có thứ tự”. Chúng ta có thể lấy một dữ liệu từ danh sách không có thứ tự nhất định một cách dễ dàng.
