CTDL và giải thuật - In chỉ số đầu tiên của phần tử đầu tiên có giá trị bằng x

Nhập vào một số nguyên dương n, tiếp theo là n số nguyên lần lượt là các phần tử trong dãy a, cuối cùng nhập số nguyên x.
In chỉ số đầu tiên của phần tử đầu tiên có giá trị bằng x, nếu không tồn tại số đó thì trả về -1.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    4
    1 2 2 4
    1

    0

    Với a = [1, 2, 2, 4] và x = 1 thì kết quả mong muốn là 0.
     
  • Test mẫu 2:
     
    Input Output

    3
    1 2 3
    4

    -1

    Với a = [1, 2, 3] và x = 4 thì kết quả mong muốn là -1.

Lý thuyết.

Giới thiệu giải thuật Tìm kiếm nội suy (Interpolation Search).

Tìm kiếm nội suy (Interpolation Search) là biến thể cải tiến của tìm kiếm nhị phân (Binary Search). Để giải thuật tìm kiếm này làm việc chính xác thì tập dữ liệu phải được sắp xếp.

Binary Search có lợi thế lớn về độ phức tạp thời gian khi so sánh với Linear SearchLinear Search có độ phức tạp trường hợp xấu nhất là Ο(n) trong khi Binary Search là Ο(log n).

Có một số tình huống mà vị trí của dữ liệu cần tìm có thể đã được biết trước. Ví dụ, trong trường hợp danh bạ điện thoại, nếu chúng ta muốn tìm số điện thoại của Hải chẳng hạn. Trong trường hợp này, Linear Search và cả Binary Search có thể là chậm khi thực hiện tìm kiếm, khi mà chúng ta có thể trực tiếp nhảy tới phần không gian bộ nhớ có tên bắt đầu với H được lưu giữ.

Xác định vị trí trong Interpolation Search.

Trong Binary Search, nếu dữ liệu cần tìm không được tìm thấy thì phần còn lại của danh sách được phân chia thành hai phần: phần bên trái (chứa giá trị nhỏ hơn) và phần bên phải (chứa giá trị lớn hơn). Sau đó tiến trình tìm kiếm được thực hiện trên một trong hai phần này.

mid = (l+r)/2.

 

Tìm kiếm nội suy tìm kiếm một phần tử cụ thể bằng việc tính toán vị trí dò (Probe Position). Ban đầu thì vị trí dò là vị trí của phần tử nằm ở giữa nhất của tập dữ liệu.

Nếu tìm thấy phần tử đó thì chỉ mục của phần tử được trả về.
Để chia danh sách thành hai phần, chúng ta sử dụng phương thức sau:

mid = l + (r-l)*(x-a[l])/(a[r]-a[l])

Trong đó tỉ số (x-a[l])/(a[r]-a[l]) dùng để ước lượng ví trí của x ở trong đoạn từ l đén r.

Nếu phần tử cần tìm có giá trị lớn hơn phần tử ở giữa thì phần tử cần tìm sẽ ở mảng con bên phải phần tử ở giữa và chúng ta lại tiếp tục tính vị trí dò, nếu không phần tử cần tìm sẽ ở mảng con bên trái phần tử ở giữa. Tiến trình này tiến tụp diễn ra trên các mảng con cho tới khi kích cỡ của mảng con giảm về 0.

Độ phức tạp thời gian chạy của Interpolation Search là Ο(log (log n)), trong khi của Binary Search là Ο(log n).

Xem ví dụ sau để biết cách hoạt động của Interpolation Search:

Tìm ví trí của x = 20 trong dãy a = [1, 3, 5, 7, 8, 9, 10, 15, 17, 20, 25, 30]

Ta dùng biến l để lưu chỉ số đầu của dãy cần xết, biến r để lưu chỉ số cuối của dãy cần xét, ban đầu l = 0 và r = n-1.

Với mỗi bước ta sẽ cần tìm vị trí mid = l + (r-l)*(x-a[l])/(a[r]-a[l]). So sánh a[mid] với x.

Với mid = l + (r-l)*(x-a[l])/(a[r]-a[l]) = 7, với a[7] = 15 < x. Lúc này ta gán l = mid + 1 và tiếp tục thực hiện.

Với mid = l + (r-l)*(x-a[l])/(a[r]-a[l]) = 8, với a[8] = 17 < x. Lúc này ta gán l = mid + 1 và tiếp tục thực hiện.

Với mid = l + (r-l)*(x-a[l])/(a[r]-a[l]) = 9, với a[9] = 20 = x. Trả về giá trị mid và kết thúc.

Nếu như khi a[l] = a[r] hoặc x > a[r] hoặc x < a[l] thì ta kiểm tra giá trị của a[l], nếu a[l] = x thì trả về giá trị l, ngược lại đưa ra -1.

Code mẫu C++:

int interpolationSearch(int a[], int n, int x){
	int l = 0, r = n-1;
	while (a[r] != a[l] && x >= a[l] && x <= a[r]){
		int mid = l + (r-l)*(x-a[l])/(a[r]-a[l]);
		if (a[mid] < x){
			l = mid + 1;
		} else if (a[mid] > x) {
			r = mid - 1;
		} else{
			if (mid > 0 && a[mid-1] == x){
				r = mid - 1;
			} else {
				return mid;
			}
		}
	}
	if (a[l] == x){
		return l;
	}
	return -1;
}

 

Ta thấy điều kiện vòng while của hàm tìm kiếm nội suy nó khác so với tìm kiếm nhị phân, lý do là chỉ số chọn làm key (mid) phải có giá trị nằm trong khoảng 0 đến n-1. và mid = l + (r-l)*(x-a[l])/(a[r]-a[l]).

  • Phải kiếm tra a[l] != a[r], phải kiểm tra phần này tránh trường hợp a[l] = a[r] dãn tới tình trạng chia cho số 0. Nếu a[l] = a[r] ta dừng vòng lặp và so sánh giá trị của đoạn cần tìm cho x.
  • Để kiểm soát chỉ số mid nằm trong khoảng từ 0 đến n-1 ta phải kiểm tra x >= a[l] && x <= a[r] tránh tình trạng chỉ số mid < 0 hoặc mid > n-1.
    Ví dụ như với dãy a = [1, 2, 3] và số cần tìm kiếm là x = 5.
    Nếu ta áp dụng công thức tính mid thì ta đươc mid = 4, không nằm trong khoảng chỉ số của dãy là từ 0 đến n-1, rất cả khả năng dẫn tới lỗi trong quá trình thực hiện.

Hướng dẫn bài tập.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

int interpolationSearch(int a[], int n, int x){
	int l = 0, r = n-1;
	while (a[r] != a[l] && x >= a[l] && x <= a[r]){
		int mid = l + (r-l)*(x-a[l])/(a[r]-a[l]);
		if (a[mid] < x){
			l = mid + 1;
		} else if (a[mid] > x) {
			r = mid - 1;
		} else{
			if (mid > 0 && a[mid-1] == x){
				r = mid - 1;
			} else {
				return mid;
			}
		}
	}
	if (a[l] == x){
		return l;
	}
	return -1;
}

int a[100];
int main(){
	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	cin >> x;
	cout << interpolationSearch(a, n, x);
	
	return 0;
}