Home Theory Sorted/Ordered Linear Search

# Sorted/Ordered Linear Search

0 comment

If the elements of the array are already sorted then in many cases we don’t have to scan the complete array to see if the element is there in the given array or not. In the given algorithm below, it can be seen that, at any point if the value at arr[i] is greater than the data to be searched then we just return -1 without searching the remaining array.

#include<stdio.h>

// a function to search "data" in an array "arr" of size "size"
// returns 1 if the element is present else 0
int orderedLinearSearch(int arr[], int size, int data)
{
int found_flag = 0;

int i;
for(i=0;i<size;i++)
{
//loop through the entire array and search for the element
if(arr[i] == data)
{
// if the element is found, we change the flag and break the loop
found_flag = 1;
break;
}
// here is an additional check
else if(arr[i] > data)
break;
}

return found_flag;
}

//driver program to test the function
int main(void)
{
int arr[10] = {2, 6, 4, 10, 8, 1, 9, 5, 3, 7};

int to_search = 5;

if(orderedLinearSearch(arr,10,to_search))
printf("FOUND");
else

return 0;
}


Time complexity for this algorithm is O(n). This is because in the worst case we need to scan the complete array. But in the average case it reduces the complexity even though the growth rate is same. Space complexity:- O(1).

Note: We can make the above algorithm even faster by making further improvements by incrementing the index at a faster rate. This will reduce the number of comparisons for searching in the sorted list.

0 comment

#### You may also like

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More