Home Theory Sorted/Ordered Linear Search

Sorted/Ordered Linear Search

by nikoo28
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
		printf("NOT FOUND");

	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

Enclose codes in [code lang="JAVA"] [/code] tags

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