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 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 =0; i --]{if [array[i]==x]{
return i;
}
}
}
int main[void]{
int array[] = {5, 4, 6, 7, 2, 8, 7, 3};
int x;
int n= SIZE_OF_ARRAY[array];
x = 7;
int k1 = find_last_x[array, n , x];
printf["Vi tri cuoi cung cua so %d trong mang array la %d\n", x,k1];
x = 4;
int k2 = find_last_x[array, n , x];
printf["Vi tri cuoi cung cua so %d trong mang array la %d\n", x,k2];
return 0;
}
Kết quả phép tìm vị trí cuối cùng của phần tử x trong mảng C như sau:
| Vi tri cuoi cung cua so 7 trong mang array1 la 6 Vi tri cuoi cung cua so 4 trong mang array2 la 1 |
Tìm số chẵn lẻ cuối cùng trong mảng C
Để tìm số chẵn cuối cùng trong mảng, chúng ta đơn giản tạo một vòng lặp để lấy từng phần tử từ cuối mảng về đầu mảng, và kiểm tra xem phần tử đó có phải là số chẵn không.
Số chẵn đầu tiên được tìm thấy chính là số chẵn cuối cùng trong mảng C.
Một cách tương tự thì chúng ta cũng có thể tìm số lẻ cuối cùng trong mảng với phương pháp này.
Về việc kiểm tra một phần tử là số chẵn hay số lẻ, chúng ta sẽ dùng tới một trong 2 phương pháp mà Kiyoshi đã hướng dẫn trong bài:
- Xem thêm: Kiểm tra số chẵn lẻ trong C
Và chúng ta viết chương trình tìm số chẵn lẻ cuối cùng trong mảng như sau:
int check_odd_even[int n]{ int flag = 1; if[ n % 2 == 0 ] flag= 0; return flag; } int find_last_odd[int array[], size_t n]{ for [size_t i = n-1; i >=0; i --]{ int x = array[i]; if [check_odd_even[x]==0]{ return x; } } } int find_last_even[int array[], size_t n]{ for [size_t i = n-1; i >=0; i --]{ int x = array[i]; if [check_odd_even[x]==1]{ return x; } } } int main[void]{ int array[] = {5, 4, 6, 7, 2, 8, 7, 3}; int n= SIZE_OF_ARRAY[array], k; k = find_last_odd[array, n]; printf["So chan cuoi cung trong mang la %d\n", k]; k = find_last_even[array, n]; printf["So le cuoi cung trong mang la %d\n", k]; return 0; } |
Kết quả phép tìm số chẵn lẻ cuối cùng trong mảng C như sau:
| So chan cuoi cung trong mang la 8 So le cuoi cung trong mang la 3 |
Tìm số âm dương cuối cùng trong mảng C
Để tìm số dương cuối cùng trong mảng, chúng ta đơn giản tạo một vòng lặp để lấy từng phần tử từ cuối mảng về đầu mảng, và kiểm tra xem phần tử đó có phải là số dương không.
Số dương đầu tiên được tìm thấy chính là phần tử dương cuối cùng trong mảng C.
Một cách tương tự thì chúng ta cũng có thể tìm số âm cuối cùng trong mảng với phương pháp này.
Về việc kiểm tra một phần tử là số âm hay số dương, chúng ta đơn giản so sánh số đó với 0. Bạn cũng có thể dùng tới hàm tự tạo mà Kiyoshi đã hướng dẫn trong bài:
- Xem thêm: Kiểm tra số âm số dương trong C
Và chúng ta viết chương trình tìm số âm số dương cuối cùng trong mảng như sau:
int main[void]{ int array[] = {5, 4, -6, 7, -2, 8, 7, 3}; int n= SIZE_OF_ARRAY[array]; for [size_t i = n-1; i >=0; i --]{ if [array[i]>0]{ printf["So duong cuoi cung trong mang la %d\n", array[i]]; break; } } for [size_t i = n-1; i >=0; i --]{ if [array[i] Chủ Đề |