Tìm kiếm

Tìm kiếm là quá trình xác định vị trí của một phần tử cụ thể trong một dãy phần tử. 

Thuật toán tìm kiếm là thuật toán nhận một đối số x và cố tìm phần tử có giá trị là x trong một tập hợp giá trị cho trước. Vì vậy, việc tìm kiếm phần tử có giá trị đó có thể không thành công nếu phần tử ấy không tồn tại. 

Có nhiều kỹ thuật và phương pháp tìm kiếm, nhưng trong C++ bạn sẽ học về:

• Tìm kiếm tuyến tính
• Tìm kiếm nhị phân

Tìm kiếm tuyến tính

Tìm kiếm tuyến tính là kỹ thuật tìm kiếm cơ bản nhất và cũng dễ triển khai trong C++. Như tên gọi, trong tìm kiếm tuyến tính, khóa cần tìm được so sánh lần lượt với từng phần tử của dãy dữ liệu cho đến khi tìm thấy hoặc dãy kết thúc.

Linear Search(sequence, key)
	for each item in sequence:
		if item == key
			return item's index

Trong code thực tế, tìm kiếm tuyến tính sẽ trông như thế này:

int linear_search(int array[], int n, int x)
{
	for(int i = 0; i < n; i++)
		if(array[i] == x)
			return i;
	return 0;
}

int main()
{
	int array[] = {1, 2, 3, 4, 5};
	int n = 5;
	int x = 3;
	
	cout << "The index of the element " << x << " is " << linear_search(array, n, x);

Output:
The index of the element 3 is 2

Như bạn có thể thấy trong đoạn code trên, hàm tìm kiếm tuyến tính về cơ bản sẽ lặp qua dãy phần tử cho đến khi tìm thấy kết quả khớp. Nếu không tìm thấy kết quả khớp, hàm sẽ trả về -1.

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 vị trí của một phần tử, nhưng mảng phải được sắp xếp.
Thuật toán tìm kiếm nhị phân sử dụng kỹ thuật "chia để trị" để tìm khóa. Dãy phần tử liên tục được chia đôi, rồi thuật toán tìm phần tử trong nửa gần với vị trí cần tìm hơn.

Giả sử chúng ta đang tìm phần tử x = 4

Đây là dạng code của thuật toán tìm kiếm nhị phân.

int binarySearch(int array[], int x, int left, int right) {
  
  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      left = mid + 1;

    else
      right  = mid - 1;
  }

  return -1;
}

int main()
{
    int array[] = {1, 5, 8, 10, 20};
    int x = 10;
    int n = 5;
    int result = binarySearch(array, x, 0, n - 1);
    
    if(result == -1)
    	cout << "Not found.";
    else
    	cout << "The element is found at " << result;

Output:
The element is found at 3

Hãy nhớ tìm kiếm là gì, mục đích của nó và chúng ta dùng nó để làm gì. Hãy nhớ cách triển khai tìm kiếm tuyến tính và tìm kiếm nhị phân. Tiếp tục luyện tập các kỹ thuật nâng cao trong C++ thông qua các bài tập.