#include <stdio.h>
int searchElementInRotatedArray(int arr[], int start, int end, int key) {
while(start < end) {
int mid = (start + end) / 2;
if(arr[mid] == key) {
return 1;
}
if(arr[start] <= arr[mid]) {
if((key >= arr[start]) && (key <= arr[mid])) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if((key >= arr[mid]) && (key <= arr[end])) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return 0;
}
int main() {
int len, num;
printf("Enter Length of Array: ");
scanf("%d", &len);
int arr[len];
printf("Enter Elements of Array: ");
for(int loop = 0; loop < len; loop++) {
scanf("%d ", &arr[loop]);
}
printf("Enter Element to Search: ");
scanf("%d", &num);
(searchElementInRotatedArray(arr, 0, len, num))?printf("Key Found\n"):printf("Key Not Found\n");
return 0;
}
int searchElementInRotatedArray(int arr[], int start, int end, int key) {
while(start < end) {
int mid = (start + end) / 2;
if(arr[mid] == key) {
return 1;
}
if(arr[start] <= arr[mid]) {
if((key >= arr[start]) && (key <= arr[mid])) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if((key >= arr[mid]) && (key <= arr[end])) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return 0;
}
int main() {
int len, num;
printf("Enter Length of Array: ");
scanf("%d", &len);
int arr[len];
printf("Enter Elements of Array: ");
for(int loop = 0; loop < len; loop++) {
scanf("%d ", &arr[loop]);
}
printf("Enter Element to Search: ");
scanf("%d", &num);
(searchElementInRotatedArray(arr, 0, len, num))?printf("Key Found\n"):printf("Key Not Found\n");
return 0;
}
No comments:
Post a Comment