Trong hướng dẫn này, bạn sẽ học về tìm kiếm tuyến tính. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của tìm kiếm tuyến tính C, C ++, Java và Python.
Tìm kiếm tuyến tính là thuật toán tìm kiếm đơn giản nhất để tìm kiếm một phần tử trong danh sách theo thứ tự tuần tự. Chúng tôi bắt đầu từ một đầu và kiểm tra mọi phần tử cho đến khi phần tử mong muốn không được tìm thấy.
Tìm kiếm tuyến tính hoạt động như thế nào?
Các bước sau được thực hiện để tìm kiếm một phần tử k = 1trong danh sách bên dưới.
Mảng được tìm kiếm
- Bắt đầu từ phần tử đầu tiên, so sánh k với mỗi phần tử x.
So sánh với từng phần tử - Nếu
x == k, trả về chỉ mục.
Phần tử được tìm thấy - Khác, không tìm thấy trở lại.
Thuật toán tìm kiếm tuyến tính
LinearSearch (mảng, khóa) cho từng mục trong mảng nếu giá trị item == trả về chỉ số của nó
Ví dụ về Python, Java và C / C ++
Python Java C C ++ # Linear Search in Python def linearSearch(array, n, x): # Going through array sequencially for i in range(0, n): if (array(i) == x): return i return -1 array = (2, 4, 0, 1, 9) x = 1 n = len(array) result = linearSearch(array, n, x) if(result == -1): print("Element not found") else: print("Element found at index: ", result)
// Linear Search in Java class LinearSearch ( public static int linearSearch(int array(), int x) ( int n = array.length; // Going through array sequencially for (int i = 0; i < n; i++) ( if (array(i) == x) return i; ) return -1; ) public static void main(String args()) ( int array() = ( 2, 4, 0, 1, 9 ); int x = 1; int result = linearSearch(array, x); if (result == -1) System.out.print("Element not found"); else System.out.print("Element found at index: " + result); ) )
// Linear Search in C #include int search(int array(), int n, int x) ( // Going through array sequencially for (int i = 0; i < n; i++) if (array(i) == x) return i; return -1; ) int main() ( int array() = (2, 4, 0, 1, 9); int x = 1; int n = sizeof(array) / sizeof(array(0)); int result = search(array, n, x); (result == -1) ? printf("Element not found") : printf("Element found at index: %d", result); )
// Linear Search in C++ #include using namespace std; int search(int array(), int n, int x) ( // Going through array sequencially for (int i = 0; i < n; i++) if (array(i) == x) return i; return -1; ) int main() ( int array() = (2, 4, 0, 1, 9); int x = 1; int n = sizeof(array) / sizeof(array(0)); int result = search(array, n, x); (result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result; )
Tìm kiếm tuyến tính phức tạp
Độ phức tạp về thời gian: O (n)
Không gian phức tạp: O(1)
Ứng dụng tìm kiếm tuyến tính
- Đối với các hoạt động tìm kiếm trong các mảng nhỏ hơn (<100 mục).
