Cho một mảng số nguyên Arr [] chứa các số nguyên theo thứ tự bất kỳ. Mục đích là để tìm số nguyên đầu vào val có trong mảng bằng cách sử dụng tìm kiếm đệ quy trên mảng.
Nếu không tìm thấy val trong mảng đầu vào Arr [] thì trả về -1. In chỉ số của val nếu được tìm thấy trong Arr [].
Ví dụ
Đầu vào −Arr [] ={11,43,24,50,93,26,78} val =26
Đầu ra - 26 được tìm thấy ở chỉ mục 5
Giải thích -
Elements in the array start from index 0 to index=array length -1. First index=0 last index=6 : 11 != 26, 78 != 26 → 0+1 , 6-1 First index=1 last index=5 : 43 != 26, 26 = 26 return 5 26 is present at index 5.
Đầu vào - Arr [] ={11,43,24,50,93,26,78} val =66
Đầu ra - 66 không có mặt
Giải thích -
Elements in the array start from index 0 to index=array length -1. First index=0 last index=6 : 11 != 66, 78 != 66 → 0+1 , 6-1 First index=1 last index=5 : 66 != 26, 66 != 26 → 1+1 , 5-1 First index=2 last index=4 : 24 != 66, 93 != 66 → 2+1 , 4-1 First index=3 last index=3 : 50 != 26, 50 != 26 → 3+1 , 3-1 First index=3 last index=2 3>2 end 66 not found.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng tôi sẽ duyệt mảng một cách tuyến tính từ cả hai đầu. So sánh giá trị đầu vào với các phần tử ở cả hai đầu. Nếu được tìm thấy, sau đó trả về chỉ mục khác kiểm tra đệ quy các phần tử tiếp theo với chỉ mục đầu tiên =chỉ mục đầu tiên trước + 1 và chỉ mục cuối cùng =chỉ mục cuối cùng trước đó-1. Trong trường hợp không tìm thấy chỉ mục đầu tiên> phần tử thời hạn cuối cùng.
-
Lấy mảng đầu vào Ar [] với các phần tử nguyên.
-
Lấy phần tử được tìm kiếm là val.
-
Hàm searchRec (int arr [], int start, int end, int num) nhận một mảng, các chỉ mục đầu tiên và cuối cùng và giá trị num sẽ được tìm kiếm và trả về chỉ mục nếu được tìm thấy.
-
Lấy kết quả biến là -99.
-
Nếu arr [start] ==num thì đặt kết quả là bắt đầu
-
Nếu arr [end] ==num thì đặt kết quả là end
-
if (start> end) then set result =-1. Như đã duyệt qua toàn bộ mảng
-
Nếu kết quả có giá trị khác -99 thì trả về kết quả khác tìm kiếm đệ quy bằng cách sử dụng searchRec (arr, start + 1, end - 1, num)
-
Bên trong kiểm tra chính giá trị trả về và kết quả in tương ứng
Ví dụ
#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<<" is not present" ;
}
else{
cout<<val<<" found at index "<<pos;
}
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
56 found at index 3