Linear Search (Thuật toán tìm kiếm tuyết tính) Và Binary Search (Thuật toán tìm kiếm nhị phân)

1. Linear Search

a. Khái niệm

- Thuật toán tìm kiếm tuyến tính là duyệt tuần tự từng phần tử trong mảng rồi so sánh giá trị tìm kiếm với từng phần tử trong mảng.

- Đặc điểm của thuật toán Linear Search:

• Có thể tìm kiếm ngay cả khi mảng chưa được sắp xếp.
• Thuật toán mạnh hơn Binary Search trong việc tìm kiếm trong mảng chưa sắp xếp.
• Được áp dụng trong các bài toán tìm vị trí đầu tiên, tìm vị trí cuối cùng, đếm số lần xuất hiện của các phần tử trong mảng.

Ví dụ: Nếu trong danh sách 1 3 4 5 6 có 5 phần tử mà ta cần tìm 4 thì nó sẽ duyệt 1->3->4 đến khi thấy 4 trả về true còn duyệt hết mà không thấy trả về false.

b. Thực hành

Ngôn Ngữ: C++

#include <iostream> 
#include <vector>
using namespace std;

bool linear_search(vector<long long> &a, long long x)
{
	for(int i = 0; i < a.size(); i++)
	{
     if(a[i] == x)
	 {
		return true;
	 }
	}
	return false;
}

int main()
{
	// Code tăng tốc 
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	//------End-------//
	long long n, x; 
	cin >> n >> x; 
	vector<long long> a(n); 
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	} 
	if(linear_search(a, x) == true) // if(linear_search(a, x)) đều đúng
	{
		cout << "Co ton tai!" << endl;
	}
	else {
		cout << "Khong ton tai!" << endl;
	}
	return 0;
}
    

2. Binary Search

a. Khái niệm

- Thuật toán tìm kiếm nhị phân (Binary Search) là thuật toán mà trong đó nó tìm kiếm từ đoạn left->right của mảng, ở mỗi bước của thuật toán nó sẽ tìm vị trí gốc là giữa (gọi là mid/pivot) và so sánh với phần tử cần tìm trong bước đó. Nếu phần tử cần tìm kiếm bằng phần tử tại vị trí giữa thuật toán sẽ trả về true, nếu không tuỳ phần tử lớn hơn vị trí giữa hay bé hơn vị trí giữa mà ta lược đi đoạn đó (không phải xoá khỏi mảng) tức là không tìm kiếm nữa - sau tất cả bước lặp mà không tìm thấy phần tử thoả mãn thì thuật toán trả về false sau khi kết thúc vòng lặp do (left<=right).

- Đặc điểm của Binary Search:

• Sắp xếp nhanh hơn Linear Search với trường hợp mảng ĐÃ SẮP XẾP.
• Chỉ HOẠT ĐỘNG ĐƯỢC với mảng ĐÃ SẮP XẾP.
• Không nên Sắp Xếp lại mảng sau đó dùng Binary Search thay vì dùng Linear Search (Nhanh hơn nhiều).
• Được ứng dụng vào các bài toán như Linear Search nhưng với điều kiện mảng phải được sắp xếp sẵn.
• Right = Pivot - 1 lấy mảng nhỏ, Left = Pivot + 1 lấy mảng lớn.

- Các bước hoạt động của Binary Search:

1. Bắt đầu vòng lặp Left <= Right.
2. Chọn phần tử ngay giữa.
3. Nếu phần tử giữa thoả mãn phần tử cần tìm trả về true và kết thúc hàm.
4. Nếu phần tử giữa > pivot thì lược đi bên phải bằng pivot - 1, dịch bên phải ra sau pivot tức là thành mảng "nhỏ hơn pivot và chứa phần tử cần tìm" sau khi lược nhưng các phần tử bị lược không bị xoá ra khỏi mảng.
5. Nếu phần tử giữa < pivot thì lược đi bên phải bằng pivot + 1, dịch bên trái ra sau pivot tức là thành mảng "lớn hơn pivot và chứa phần tử cần tìm" sau khi lược nhưng các phần tử bị lược không bị xoá ra khỏi mảng.
6. Sau khi vòng lặp kết thúc mà vẫn không tìm thấy thì kết thúc vòng lặp ngay và "return false" tức là không tìm thấy phần tử vì cả vòng lặp không tìm thấy.

b. Thực hành

Ngôn Ngữ: C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool binary_search(vector<long long> &a, long long left, long long right, long long x)
{
	while(left <= right)
	{
		long long pivot = left + ((right - left) / 2); // Khoảng cách + phần tử đầu = khoảng cách thực
		if(a[pivot] == x) {
			return true;
		}
		else if(a[pivot] > x) {
			right = pivot - 1;
		}
		else {
                        left = pivot + 1;
		}
	}
	return false;
}

int main()
{
	// Code tăng tốc 
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	//------End-------//
	long long n, x; 
	cin >> n >> x; 
	vector<long long> a(n); 
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	} 
	sort(a.begin(), a.end()); // Binary search chỉ hoạt động với mảng sắp xếp
	if(binary_search(a, 0, n - 1, x) == true) // if(binary_search(a, 0, n - 1, x)) đều đúng
	{
		cout << "Co ton tai!" << endl;
	}
	else {
		cout << "Khong ton tai!" << endl;
	}
	return 0;
}