CTDL và giải thuật - Tìm vị trí của phần tử đầu tiên có giá trị bằng x

Cho số nguyên dương n, tiếp theo là n số nguyên cũng một dãy a, cuối cùng là một số x, biết dãy là dãy không giảm.
Hãy đưa ra chỉ số của phần tử đầu tiên có giá trị bằng x, nếu không tồn tại giá trị đó đưa ra -1.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    4
    1 2 3 4
    3

    2

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

    4
    2 2 2 2
    2

    0

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

Lý thuyết.

Giới thiệu giải thuật tìm kiếm nhị phân (Binary Search).

Binany Search (Tìm kiếm nhị phân) là một giải thuật tìm kiếm nhanh với độ phức tạp thời gian chạy là Ο(log n). Giải thuật tìm kiếm nhị phân làm việc dựa trên nguyên tắc chia để trị (Divide and Conquer). Để giải thuật này có thể làm việc một cách chính xác thì tập dữ liệu nên ở trong dạng đã được sắp xếp.

Binary Search tìm kiếm một phần tử cụ thể bằng cách so sánh phần tử tại vị trí giữa nhất của tập dữ liệu. Nếu tìm thấy kết nối thì chỉ mục của phần tử được trả về. Nếu phần tử cần tìm là lớn hơn giá trị phần tử giữa thì phần tử cần tìm được tìm trong mảng con nằm ở bên phải phần tử giữa, nếu không thì sẽ tìm ở trong mảng con nằm ở bên trái phần tử giữa. Tiến trình sẽ tiếp tục như vậy trên mảng con cho tới khi tìm hết mọi phần tử trên mảng con này.

Chúng ta xem ví dụ sau để hiểu rõ cách hoạt động của Binary Search:

Tìm vị trí đầu tiên của x = 10 trong dãy a = [1, 2, 5, 8, 10, 13, 17, 24, 30, 50, 55, 61].

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)/2. So sánh a[mid] với x.

Với mid = (l+r)/2 = (0+11)/2 = 5, a[5] = 13 ≥ 10. Ta dễ nhận thấy ràng với a[mid] ≥ x thì phần tử cần tìm chỉ nằm trong khoảng từ vị trí l đến mid.
Lúc này ta có thể thay đổi r = mid.

Với mid = (l+r)/2 = (0+5)/2 = 2. Với a[2] = 5 < 10. Với a[mid] < x thì dãy cần xét sẽ là dãy từ vị trí mid+1 đến r.
Cập nhật l = mid+1.

Với mid = (l+r)/2 = (3+5)/2 = 4, với a[4] = 10, tuy đã tìm được phần tử bằng x những có thể đó chưa phải là phần tử đầu tiên nên ta tiếp tục xét đoạn l đến mid.

Với mid = (l+r)/2 = (3+4)/2 = 3. Với a[3] = 8 < 10. Cập nhất l = mid+1. Lúc này l = r = 4. Lúc này ta cần kiểm tra a[l] nếu a[l] bằng x thì đưa ra l, ngược lại đưa ra -1.

Code C++ mẫu:

int BinSearch(int a[], int n, int x){
	int l = 0, r = n-1;
	while (l < r){
		int mid = (l+r)/2;
		if (a[mid] < x){
			l = mid+1;
		}
		else{
			r = mid;
		}
	}
	if (a[l] == x){
		return l;
	}
	return -1;
}

 

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

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

int BinSearch(int a[], int n, int x){
	int l = 0, r = n-1;
	while (l < r){
		int mid = (l+r)/2;
		if (a[mid] < x){
			l = mid+1;
		}
		else{
			r = mid;
		}
	}
	if (a[l] == x){
		return l;
	}
	return -1;
}

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