二分搜索演算法的功能

⑴ 二分查找法

二分查找法的解釋如下：

二分查找法也稱折半查找法，是一種在有序數組中查找某一特定元素的搜索演算法。我們可以從定義可知，運用二分搜索的前提是數組必須是有序的，這里需要注意的是，我們的輸入不一定是數組，也可以是數組中某一區間的起始位置和終止位置。

如果想要在數組中查找一個數，最基本的方法就是暴力解法：一次遍歷，這時候時間復雜度是O（N），二分查找就是其中的一種優化，時間復雜度是O（logN）；具體做法是一步一步逼近直到找到。前提是數組需要是一個排序數組。

演算法要求：

1、必須採用順序存儲結構。

2、必須按關鍵字大小有序排列。

比較次數

計算公式：

當順序表有n個關鍵字時：

查找失敗時，至少比較a次關鍵字；查找成功時，最多比較關鍵字次數是b。

注意：a，b，n均為正整數。

⑵ 二分查找演算法

二分查找演算法，該演算法要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。如果一個序列是無序的或者是鏈表，那麼該序列就不能使用二分查找。

二分查找演算法原理：若待查序列為空，則返回-1，並退出演算法；若待查序列不為空，則將它的中間元素與目標數值進行比較，判斷是否相等；若相等，則返回中間元素索引，並退出演算法；此時已查找成功。若不相等，則比較中間元素與目標數值的大小。

二分查找的一個技巧是：不要出現else，而是把所有情況用else，if寫清楚，這樣可以清楚地展現所有細節。本文都會使用else，if，旨在講清楚，讀者理解後可自行簡化。

⑶ 二分搜索演算法是利用什麼實現的演算法

二分搜索演算法是利用排除剩餘元素中一半的元素實現的演算法。

在計算機科學中，二分搜索（英語：binary search），也稱折半搜索（英語：half-interval search）、對數搜索（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜索演算法。

二分搜索演算法原理：

1、如果待查序列為空，那麼就返回－1，並退出演算法；這表示查找不到目標元素。如果待查序列不為空，則將它的中間元素與要查找的目標元素進行匹配，看它們是否相等。如果相等，則返回該中間元素的索引，並退出演算法；此時就查找成功了。如果不相等，就再比較這兩個元素的大小。

2、如果該中間元素大於目標元素，那麼就將當前序列的前半部分作為新的待查序列；這是因為後半部分的所有元素都大於目標元素，它們全都被排除了。

3、如果該中間元素小於目標元素，那麼就將當前序列的後半部分作為新的待查序列；這是因為前半部分的所有元素都小於目標元素，它們全都被排除了。

⑷ 對比順序查找、二分查找和哈希查找演算法,它們各自的特點是什麼

順序查找,二分查找和哈希查找演算法,它們各自的特點是：
1.對比順序查找的特點就是從表的第一個元素開始一個一個向下查找，如果有和目標一致的元素，查找成功;如果到最後一個元素仍沒有目標元素，則查找失敗。
2.二分查找的特點就是從表中間開始查找目標元素。如果找到一致元素，則查舉羨找成功。如果中間元素比正蠢拍目標元素小，則仍用二分查找方法查找表的後半部分(表是遞增排列的)，反之中間元素比目標元素大，則查找表的前半部分。
3.哈希演算法的特點是是使用給定數據構造哈希表，然後檔芹在哈希表上進行查找的一種演算法。先給定一個值，然後根據哈希函數求得哈希地址，再根據哈希地址查找到要找的元素。是通過數據元素的存儲地址進行查找的一種演算法。

⑸ 什麼叫java中的二分查找法

1、演算法概念。

二分查找演算法也稱為折半搜索、二分搜索，是一種在有序數組中查找某一特定元素的搜索演算法。請注意這種演算法是建立在有序數組基礎上的。

2、演算法思想。

①搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；

②如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。

③如果在某一步驟數組為空，則代表找不到。

這種搜索演算法每一次比較都使搜索范圍縮小一半。

3、實現思路。

①找出位於數組中間的值，並存放在一個變數中（為了下面的說明，變數暫時命名為temp）；

②需要找到的key和temp進行比較；

③如果key值大於temp，則把數組中間位置作為下一次計算的起點；重復① ②。

④如果key值小於temp，則把數組中間位置作為下一次計算的終點；重復① ② ③。

⑤如果key值等於temp，則返回數組下標，完成查找。

4、實現代碼。

/**
*description:二分查找。
*@paramarray需要查找的有序數組
*@paramfrom起始下標
*@paramto終止下標
*@paramkey需要查找的關鍵字
*@return
*/
publicstatic<EextendsComparable<E>>intbinarySearch(E[]array,intfrom,intto,Ekey)throwsException{
if(from<0||to<0){
("paramsfrom&lengthmustlargerthan0.");
}
if(from<=to){
intmiddle=(from>>>1)+(to>>>1);//右移即除2
Etemp=array[middle];
if(temp.compareTo(key)>0){
to=middle-1;
}elseif(temp.compareTo(key)<0){
from=middle+1;
}else{
returnmiddle;
}
}
returnbinarySearch(array,from,to,key);
}

⑹ 二分查找演算法實現（圖解）與實例

當我們要從一個序列中查找一個元素的時候，二分查找是一種非常快速的查找演算法，二分查找又叫折半查找。

它對要查找的序列有兩個要求，一是該序列必須是有序的（即該序列中的所有元素都是按照大小關系排好序的，升序和降序都可以，本文假設是升序排列的），二是該序列必須是順序存儲的。

如果一個序列是無序的或者是鏈表，那麼該序列就不能進行二分查找。之所以被查找的序列要滿足這樣的條件，是由二分查找演算法的原理決定的。

二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。

二分查找能應用於任何類型的數據，只要能將這些數據按照某種規則進行排序。然而，正因為它依賴於一個有序的集合，這使得它在處理那些頻繁插入和刪除操作的數據集時不太高效。這是因為，對於插入和操作來說，為了保證查找過程正常進行，必須保證數據集始終有序。相對於查找來說，維護一個有序數據集的代價更高。此外，元素必須存儲在連續的空間中。因此，當待搜索的集合是相對靜態的數據集時，此時使用二分查找是最好的選擇。

二分查找演算法的原理如下：

二分查找之所以快速，是因為它在匹配不成功的時候，每次都能排除剩餘元素中一半的元素。因此可能包含目標元素的有效范圍就收縮得很快，而不像順序查找那樣，每次僅能排除一個元素。

二分查找法實質上是不斷地將有序數據集進行對半分割，並檢查每個分區的中間元素。

此實現過程的實施是通過變數left和right控制一個循環來查找元素（其中left和right是正在查找的數據集的兩個邊界值）。

二分查找的時間復雜度取決於查找過程中分區數可能的最大值。對於一個有n個元素的數據集來說，最多可以進行O(㏒₂n)次分區。對於二分查找，這表示最終可能在最壞的情況下執行的檢查的次數：例如，在沒有找到目標時。所以二分查找的時間復雜度為O(㏒₂n)。

參考：
https://www.html.cn/qa/other/23018.html

https://www.cnblogs.com/idreamo/p/9000762.html