Chương 2. Thuật toán tìm kiếm

2.1. Định nghĩa về tìm kiếm

Trong môn khoa học máy tính, tìm kiếm là một quá trình tìm kiếm một đối tượng với những thuộc tính đặc trưng trong tập hợp các đối tượng. Đối tượng tìm kiếm ấy có thể là bản ghi trong một cơ sở dữ liệu, những dữ liệu cơ bản trong một mảng, đoạn văn trong file, node trên cây...

2.2. Tại sao chúng ta cần tìm kiếm?

Tìm kiếm là một trong những phần quan trọng nhất của thuật toán. Chúng ta đều biết rằng máy tính lưu trữ rất nhiều thông tin. Và để tìm kiếm thông tin ấy một cách nhanh chóng, chúng ta cần phải nhờ thuật toán tìm kiếm. Có rất nhiều các để sắp xếp thông tin giúp cho việc tìm kiếm trở nên nhanh chóng. Trong chương này, chúng ta sẽ tìm hiểu một số thuật toán tìm kiếm cơ bản.

2.3. Các thuật toán tìm kiếm cơ bản

2.3.1. Thuật toán tìm kiếm tuyến tính

2.3.1.1. Bài toán tìm kiếm

Cho trước mảng một chiều có n phần tử. Tìm phần tử data có giá trị cho trước trong mảng. Nếu phần tử đó tồn tại trong danh sách thì xuất vị trí của nó trong danh sách. Nếu phần tử đó không tồn tại trong danh sách thì trả về giá trị -1.

2.3.1.2. Ý tưởng thuật toán

Như chúng ta đã biết, tìm kiếm tuyến tính còn được gọi là tìm kiếm tuần tự, vì thế chúng ta sẽ so sánh tuần tự giá trị của x với phần tử thứ 0, phần tử thứ 1,... của danh sách cho đến khi tìm được phần tử cần tìm. Nếu không tìm thấy thì trả về giá trị -1.

2.3.1.3. Các bước của thuật toán

Bước 1: Gán i = 0 (Giá trị khởi đầu)

Bước 2: So sánh a[i] với data. Có 2 khả năng xảy ra:

• Nếu a[i] = data thì trả về giá trị i là vị trí cần tìm.
• Nếu a[i] != data thì tiếp tục bước 3.

Bước 3: i = i + 1 (Xét tiếp phần tử tiếp theo trong mảng)

• Nếu i = n thì không tìm thấy và trả về giá trị -1.
• Ngược lại, tiếp tục bước 2.

2.3.1.4. Code minh họa

int linearSearch(int a[], int n, int data) {
    for (int i = 0; i < n; i++) {
        if (a[i] == data) {
            return i;
        }
    }
    return -1;
}

• Độ phức tạp thuật toán: $O(N)$
• Trường hợp xấu nhất: Duyệt hết tất cả phần tử trong mảng
• Độ phức tạp không gian: $O(1)$

2.3.2. Thuật toán tìm kiếm nhị phân

2.3.2.1. Bài toán tìm kiếm

Cho trước một mảng một chiều có n phần tử đã được sắp xếp tăng dần hoặc giảm dần. Tìm phần tử data có giá trị cho trước trong mảng. Nếu phần tử đó tồn tại trong danh sách thì xuất vị trí của nó trong danh sách. Nếu phần tử đó không tồn tại trong danh sách thì trả về giá trị -1.

2.3.2.2. Ý tưởng thuật toán

Chúng ta sẽ so sánh data với giá trị phần tử chính giữa của mảng. Nếu như giá trị đó bằng data thì xuất ra vị trí ấy, nếu nhỏ hơn data thò quá trình tìm kiếm sẽ được tiếp tục ở nửa sau của mảng. Bằng cách này, ở mỗi phép lặp của thuật toán, chúng ta có thể loại bỏ được nửa mảng mà giá trị data chắc chắn sẽ không xuất hiện.

2.3.2.3. Các bước của thuật toán

Bước 1: Gán start = 0, end = n - 1

Bước 2: So sánh start với end

• Nếu start > end thì tìm kiếm thất bại và trả về giá trị -1
• Ngược lại:
  • Gán mid = start + (end - start) / 2 (Tránh bị tràn mảng)
  • So sánh a[mid] với data
• Nếu a[mid] = data thì trả về giá trị mid là vị trí cần tìm và kết thúc bài toán.
• Nếu a[mid] < data thì gán start = mid + 1 (tìm ở nửa bên phải)
• Nếu a[mid] > data thì gán end = mid - 1 (tìm ở nửa bên trái)

2.3.2.4. Code minh họa

• Code trực tiếp:

int binarySearch(int a[], int n, int data) {
    int start = 0;
    int end = n - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (a[mid] == data) {
            return mid;
        }
        else if (a[mid] < data) {
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
    return -1;
}

• Code bằng đệ quy (recursion):

int binarySearchRecursion(int a[], int start, int end, int data) {
    int mid = start + (end - start) / 2;
    if (start > end) {
        return - 1;
    }
    else if (a[mid] == data) {
        return mid;
    }
    else if (a[mid] < data) {
        binarySearchRecursion(a, mid + 1, end, data);
    }
    else {
        binarySearchRecursion(a, start, end - 1, data);
    }
    return -1;
}

• Độ phức tạp: $O(\log N)$
• Trường hợp xấu nhất: Không tìm thấy phần tử data trong mảng.
• Độ phức tạp không gian: $O(1)$ (code trực tiếp), $O(\log N)$ (code bằng đệ quy).

2.4. Ví dụ

- Ví dụ 1: Cho mảng a[7] = {10, 20, 30, 40, 50, 60, 70}. Hỏi phần tử data bằng 55 có tồn tại trong mảng không? Nếu có thì xuất ra vị trí của phần tử trong mảng.

Cách 1: Dùng tìm kiếm tuyến tính, duyệt từng phần tử trong mảng

#include<iostream>
using namespace std;
int main(){
	int a[] = { 10, 20, 30, 40, 50, 60, 70 };
	int find = 55;
	int pos = -1;
	int n = (sizeof(a) / sizeof(a[0]));
	for (int i = 0; i < n; i++) {
		if (a[i] == find) {
			pos = i;
			break;
		}
	}
	if (a[pos] == find) {
		cout << pos << endl;
	}
	else {
		cout << "Not Found" << endl;
	}
	return 0;
}

• Độ phức tạp: $O(N)$

Cách 2: Dùng tìm kiếm nhị phân

#include<iostream>
using namespace std;
int main() {
	int a[] = { 10, 20, 30, 40, 50, 60, 70 };
	int find = 55;
	int start = 0;
	int end = (sizeof(a) / sizeof(a[0])) - 1;
	int mid;
	while (start <= end) {
		mid = start + (end - start) / 2;
		if (a[mid] == find) {
			break;
		}
		else if (a[mid] < find) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}
	if (a[mid] == find) {
		cout << mid << endl;
	}
	else {
		cout << "Not Found" << endl;
	}
	return 0;
}

• Độ phức tạp: $O(N)$

Cách 3: Cải tiến thuật toán nhị phân (Tham khảo)

• Ở thuật toán tìm kiếm nhị phân chúng ta gán

mid = start + (end - start) / 2

• Nhưng chúng ta có thể cải tiến nó bằng cách gán

mid = start + ((find - a[start]) * (end - start)) / (a[end] - a[start])

(với find là số cần tìm)

• Việc gán như thế làm giảm phạm vi tìm kiếm và làm cho độ phức tạp thuật toán giảm xuống

#include<iostream>
using namespace std;
int main() {
	int a[] = { 10, 20, 30, 40, 50, 60, 70 };
	int find = 55;
	int start = 0;
	int end = (sizeof(a) / sizeof(a[0])) - 1;
	int mid;
    while (start <= end) {
		if (find < a[start] || find > a[end]) {
			break;
		}
        else if (a[start] == a[end]) {
            mid = start;
        }
		else {
			mid = start + ((find - a[start]) * (end - start)) / (a[end] - a[start]);
		}
        
		if (a[mid] == find) {
			break;
		}
		else if (a[mid] < find) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}
	if (a[mid] == find) {
		cout << mid << endl;
	}
	else {
		cout << "Not Found" << endl;
	}
	return 0;
}

• Độ phức tạp: $O(\log (\log N))$

- Ví dụ 2: Cho một mảng số nguyên gồm n phần tử. Viết hàm kiểm tra xem mảng đó có tồn tại cặp phần tử giống nhau hay không? Nếu có trả về 1, ngược lại trả về 0.

Cách 1: Dùng 2 vòng lặp for để kiểm tra

#include<iostream>
using namespace std;

bool kiemTraPhanTuTrungLap(int a[], int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] == a[j]) {
				return 1;
			}
		}
	}
	return 0;
}
int main() {
	int n;
	cin >> n;
	int* a;
	a = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (kiemTraPhanTuTrungLap(a, n) == 1) {
		cout << '1' << endl;
	}
	else {
		cout << '0' << endl;
	}
	return 0;
}

• Độ phức tạp: $O(N^2)$

Cách 2: Dùng thư viện STL Sort để sắp xếp mảng tăng dần, sau đó dùng tìm kiếm tuyến tính để kiểm tra

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

bool kiemTraPhanTuTrungLap(int a[], int n) {
	for (int i = 0; i < n - 1; i++) {
		if (a[i] == a[i + 1])
			return 1;
	}
	return 0;
}
int main()
{
	int n;
	cin >> n;
	int* a;
	a = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	if (kiemTraPhanTuTrungLap(a, n) == 1) {
		cout << '1' << endl;
	}
	else {
		cout << '0' << endl;
	}
	return 0;
}

• Độ phức tạp: $O(N\log N)$

- Ví dụ 3: Cho một mảng số nguyên gồm n phần tử. Gọi x là tổng của 2 phần tử bất kỳ trong mảng. Viết chương trình tìm x sao cho x có giá trị lớn nhất và x bé hơn k.

Cách 1: Dùng 2 vòng for để kiểm tra

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

int main() {
	int n, x;
	cin >> n >> x;
	int* a;
	a = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int money = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			int y = a[i] + a[j];
			if (y <= x) {
				money = max(money, y);
			}
		}
	}
	cout << money << endl;
}

• Độ phức tạp: $O(N^2)$

Cách 2: Dùng STL Sort để sắp xếp mảng tăng dần, sau đó dùng tìm kiếm tuyến tính để kiểm tra

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

int main() {
	int n, x;
	cin >> n >> x;
	int* a;
	a = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int money = 0;
	int start = 0;
	int end = n - 1;
	while (start < end) {
		int y = a[start] + a[end];
		if (y <= x) {
			money = max(money, y);
			start++;
		}
		else {
			end--;
		}
	}
	cout << money << endl;
}

• Độ phức tạp: $O(N\log N)$