天天看點

算法系列15天速成——第四天 五大經典查找【上】

在我們的生活中,無處不存在着查找,比如找一下班裡哪個mm最pl,猜一猜mm的芳齡....... 對的這些都是查找。

在我們的算法中,有一種叫做線性查找。

分為:順序查找。

        折半查找。

查找有兩種形态:

分為:破壞性查找,   比如有一群mm,我猜她們的年齡,第一位猜到了是23+,此時這位mm已經從我腦海裡面的mmlist中remove掉了。

                            哥不找23+的,是以此種查找破壞了原來的結構。

       非破壞性查找, 這種就反之了,不破壞結構。 

順序查找:

    這種非常簡單,就是過一下數組,一個一個的比,找到為止。

算法系列15天速成——第四天 五大經典查找【上】

折半查找: 這種查找很有意思,就是每次都砍掉一半,

             比如"幸運52“中的猜價格遊戲,價格在999元以下,1分鐘之内能猜到幾樣給幾樣,如果那些選手都知道折半查找,

             那結果是相當的啊。

不過要注意,這種查找有兩個缺點:

            第一: 數組必須有序,不是有序就必須讓其有序,大家也知道最快的排序也是NLogN的,是以.....嗚嗚。

            第二: 這種查找隻限于線性的順序存儲結構。

上代碼:

算法系列15天速成——第四天 五大經典查找【上】

     先前也說過,查找有一種形态是破壞性的,那麼對于線性結構的資料來說很悲慘,因為每次破壞一下,

可能都導緻數組元素的整體前移或後移。

    是以線性結構的查找不适合做破壞性操作,那麼有其他的方法能解決嗎?嗯,肯定有的,不過要等下一天分享。

ps:  線性查找時間複雜度:O(n);

         折半無序(用快排活堆排)的時間複雜度:O(NlogN)+O(logN);

         折半有序的時間複雜度:O(logN);

繼續閱讀