1. 首頁 > 生活百科 > >

查找發送邀請怎么接受 查找發

生活百科

1、引言
筆者對于計算機的研究一直停滯不前，近期想對一些算法進行復習和進一步的研究，每天都會更新一個新的算法，算法有難有易，層層遞進 。不希望能學的有多么高深，只希望在一些最基本的算法上有編碼的思路，或者在一些生產環境中會應用一些算法來解決實際問題 。
就比如今天要介紹的之一個查找算法——二分查找法 。假設要在 *** 薄中找一個名字為K大頭的人，很習慣的辦法就是從頭開始翻頁，直到進入以K打頭的部分 。但是這種 *** 的缺陷就是要逐一查找，時間較長 。
于是我們可以有另外一個思路就是每次從中間開始查找，而以K打頭的名字就在 *** 簿中間 。再舉一個簡單的場景，假設登錄Facebook時，Facebook會驗證是否為自己網站的用戶，那就必然要去數據庫中作比對，如果逐一對比則用戶等待的時間過長，影響用戶體驗，更合乎邏輯的做法是從中間開始查找，這樣就會節約很長的等待時間 。
2、二分查找法
二分查找是一種算法，其輸入是一個有序的元素列表（注意：列表必須是有序的） 。如果要查找的元素包含在列表中，二分查找則返回其位置，否則返回-1 。
2.1 二分查找法的原理
舉一個示例來講解二分查找的工作原理 。想必大家都玩過1~100的猜數字游戲，目標是以最少的次數猜到這個數字 。每次猜測后，會有人告訴你這個數和要找的數是大了還是小了 。如果我們從1開始慢慢一個一個數字進行猜測，這樣的效率是很慢的，我們通常把這樣的查找方式叫做簡單查找，更準確的說法是傻找 。

查找發送邀請怎么接受 查找發

文章插圖
猜數字游戲
比較合理的查找 *** 就是從中間開始查找，如果先猜50的情況下，如果有人給你說大了，那么我們立馬排除了后面50個數字，正確答案一定在前面50個數字中，然后我們繼續猜測中間的數字，當有人告訴你小了，那么前25個數字也就排除了 。一直循環這樣下去，你會發現沒用幾步就可以得出正確答案 。這就是二分查找的原理 。

查找發送邀請怎么接受 查找發

文章插圖
二分查找過程
2.2 二分查找法的代碼實現
在我學習的過程中，我會盡量使用Java語言來編寫算法，因為自己接觸Java的機會比較多，而且Java語言也比較好用，特此奉上Java實現二分查找法的源代碼 。
/*** 1、二分查找法 適用于有序列表或者數組*/public static int BinarySerach(int[] list, int item){//定義一個低位，并賦值數組索引為0int low = 0;//定義一個高位，并賦值數組索引為數組末尾=數組長度-1int hign = list.length - 1;/*** 開始循環查找* 查找結束條件為范圍縮小到只包含一個元素時返回*/while(low <= hign){//定義一個中間值，用于接收數組的中間索引值，因為每回都是從數組的中間開始查找int mid = (low + hign) / 2;int guess = list[mid];//如果查詢的索引值就為查找到數據，即返回if(guess == item){//返回中間索引return mid;}//如果猜測的數較大，則舍棄后半部分數據，開始在前半部分查找/*** 此時修改高位為前半部分的末尾索引*/if(guess > item){hign = mid - 1;}//如果猜測的數較小，則舍棄前半部分數據，開始在后半部分查找，此時低位索引應修改為后半部分數據//的起始索引else {low = mid + 1;}}//執行循環之后沒有查找返回-1return -1;}
2.3 運行時間
每一種算法都有自己的運行時間，而衡量運行時間的 *** 通常采用大O表示法 。大O表示法是一種比較特殊的表示 ***，指出了算法的速度有多快，根據剛才的推演，如果列表中有100個元素，最多只要猜7次就可以查找到正確答案，如果列表中包含40億個數字，最多需要猜32次 。二分查找的運行時間由此稱為對數時間（或log時間），用大O表示法表示為O(logn) 。

查找發送邀請怎么接受 查找發

文章插圖
【查找發送邀請怎么接受查找發】運行時間

    推薦閱讀