The aim of this Virtual lab is to implement an adaptive search algorithm that automatically performs linear search for an unsorted list and binary search for sorted list.
The aim of this Virtual lab is to implement an adaptive search algorithm that automatically performs linear search for an unsorted list and binary search for sorted list.
The adaptive search algorithm combines the efficiency of binary search for sorted list and the simplicity of linear search for unsorted list. It determines the nature of the given sequence of elements by checking if it is sorted or unsorted. Based on the result, it applies the appropriate search algorithm. If the list is sorted, it performs binary search; otherwise, it resorts to linear search.
Search algorithms, such as linear search and binary search, are fundamental concepts with
various applications in computer science and real-world scenarios.
Its some applications
include:
The procedure for implementing the adaptive search algorithm can be summarized as follows:
Example programs
// C++
#include < iostream >
using namespace std;
int linearSearch(const int* arr, int size, int target) {
for (int i = 0; i < size; ++i) {
if (arr[i] == target)
return i; // Found the target
}
return -1; // Target not found
}
int binarySearch(const int* arr, int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid; // Found the target
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1; // Target not found
}
struct Search{
/*
Defines a structure named 'Search' that is used to represent search results or items.
The 'Search' structure has two members:
'index' (integer): Represents the index or position of a search result or item.
'sorted' (integer): Indicates whether the search result or item is sorted.
This structure can be utilized to organize and store information
related to search operations, such as maintaining the index and sorted
status of search results in a list.
*/
int index;
int sorted;
};
Search adaptiveSearch(const int* arr, int size, int target){
Search searchResult;
searchResult.sorted =0;
searchResult.index =-1;
// Check if the list is sorted
bool isSorted = true;
for (int i = 1; i < size; ++i) {
if (arr[i] < arr[i - 1]) {
isSorted = false;
break;
}
}
if (isSorted){
searchResult.index = binarySearch(arr, size, target);
searchResult.sorted = 1;
return searchResult;}
else{
searchResult.index = linearSearch(arr, size, target);
searchResult.sorted = 0;
return searchResult;}
}
int main() {
int sizeA,target,value;//sizeB,
cin>>sizeA;//sizeB;
int list[sizeA] ;
cout<<"Enter your list:\n";
for (int i = 0;i< sizeA;i++){
cin>>value;
list[i]=value; }
cout<<"Enter the target: "; cin>>target;
Search result = adaptiveSearch(list, sizeof(list) / sizeof(list[0]), target);
if(result.sorted){
if (result.index != -1){
cout << "Binary search: Found at index " << result.index << endl;}
else{
cout << "Binary search: Not found" << endl;}
}
else{
if (result.index != -1){
cout << "Linear search: Found at index " << result.index << endl;}
else{
cout << "Linear search: Not found" << endl;}
}
}
Example
If the list is unsorted it performs Linear Search :
Suppose that the input list is = [10, 13, 9, 18, 5, 11]
and the target element
to be found in the list is 18.
If the list is sorted then perform Binary Search :
Suppose that the input list is = [17, 32, 45, 53, 57, 61, 79, 88]
We have to
find the element 79 in the list.
The adaptive search algorithm will apply appropriate searching algorithm (linear/binary) as per the ordering of the elements in the input list. It will return the index of the target element if it is found in the list or -1 if the element is not present.