Cho mảng nguyên Arr[] chứa các số nguyên theo thứ tự bất kỳ. Mục tiêu là tìm số nguyên val đầu vào có trong mảng hay không bằng tìm kiếm đệ quy trên mảng.
Nếu val không tìm thấy trong mảng Arr[] thì trả về -1. In chỉ số của val nếu tìm thấy trong Arr[].
Ví dụ
Đầu vào - Arr[] = {11,43,24,50,93,26,78}, val=26
Đầu ra - 26 tìm thấy tại chỉ số 5
Giải thích -
Các phần tử trong mảng bắt đầu từ chỉ số 0 đến chỉ số = độ dài mảng -1. Chỉ số đầu=0 chỉ số cuối=6: 11 != 26, 78 != 26 → 0+1, 6-1 Chỉ số đầu=1 chỉ số cuối=5: 43 != 26, 26 = 26 trả về 5. 26 có mặt tại chỉ số 5.
Đầu vào - Arr[] = {11,43,24,50,93,26,78}, val=66
Đầu ra - 66 không có trong mảng
Giải thích -
Các phần tử trong mảng bắt đầu từ chỉ số 0 đến chỉ số = độ dài mảng -1. Chỉ số đầu=0 chỉ số cuối=6: 11 != 66, 78 != 66 → 0+1, 6-1 Chỉ số đầu=1 chỉ số cuối=5: 66 != 26, 66 != 26 → 1+1, 5-1 Chỉ số đầu=2 chỉ số cuối=4: 24 != 66, 93 != 66 → 2+1, 4-1 Chỉ số đầu=3 chỉ số cuối=3: 50 != 26, 50 != 26 → 3+1, 3-1 Chỉ số đầu=3 chỉ số cuối=2, 3>2 kết thúc, 66 không tìm thấy.
Phương pháp sử dụng trong chương trình dưới đây
Trong phương pháp này, duyệt mảng tuyến tính từ cả hai đầu. So sánh giá trị đầu vào với phần tử ở cả hai đầu. Nếu tìm thấy thì trả về chỉ số, ngược lại đệ quy kiểm tra các phần tử tiếp theo với chỉ số đầu = chỉ số đầu trước +1 và chỉ số cuối = chỉ số cuối trước -1. Trường hợp chỉ số đầu > chỉ số cuối thì phần tử không tìm thấy.
Nhập mảng Ar[] với các phần tử nguyên.
Nhập phần tử cần tìm val.
Hàm searchRec(int arr[], int start, int end, int num) nhận mảng, chỉ số đầu, cuối và giá trị num cần tìm, trả về chỉ số nếu tìm thấy.
Khai báo biến result = -99.
Nếu arr[start] == num thì gán result = start.
Nếu arr[end] == num thì gán result = end.
Nếu (start > end) thì gán result = -1 (đã duyệt hết mảng).
Nếu result khác -99 thì trả về result, ngược lại tìm kiếm đệ quy bằng searchRec(arr, start + 1, end - 1, num).
Trong main kiểm tra giá trị trả về và in kết quả tương ứng.
Ví dụ mã
#include<bits/stdc++.h> using namespace std; int searchRec(int arr[], int start,int end, int num){ int result=-99; if (start > end){ result= -1; } if (arr[start] == num){ result=start; } if (arr[end] == num){ result=end; } if( result!=-99){ return result; } return searchRec(arr, start + 1, end - 1, num); } int main(){ int Arr[] = {11,43,22,56,33,26,78}; int i; int len = sizeof(Arr) / sizeof(Arr[0]); int val = 56; int pos = searchRec(Arr, 0, len - 1, val); if (pos == -1){ cout<<val<<" không có trong mảng" ; } else{ cout<<val<<" tìm thấy tại chỉ số "<<pos; } return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
56 tìm thấy tại chỉ số 3