首页 > 其他 > 详细

有序线性搜索(Sorted/Ordered Linear Search)

时间:2015-08-10 21:50:28      阅读:112      评论:0      收藏:0      [点我收藏+]

如果数组元素已经排过序(升序),那我们搜索某个元素就不必遍历整个数组了。在下面给出的算法代码中,到任何一点,假设当前的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)。

注:我们还可以增加索引增加的速率来提高算法速度。这样会减少算法中比较的次数。但这样会有几率跳过所要搜索的数据。

有序线性搜索(Sorted/Ordered Linear Search)

原文:http://www.cnblogs.com/programnote/p/4719148.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!