如果数组元素已经排过序（升序），那我们搜索某个元素就不必遍历整个数组了。在下面给出的算法代码中，到任何一点，假设当前的arr[i]值大于搜索的值data，就可以停止搜索了。
#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;
}
算法的时间复杂度为O(n)。这是因为在最差的情况下我们仍然要搜索整个数组。虽然增长率和无序线性搜索一样，但在平均情况下减少了复杂度。
空间复杂度为O(1)。
注：我们还可以增加索引增加的速率来提高算法速度。这样会减少算法中比较的次数。但这样会有几率跳过所要搜索的数据。