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.