二分查找演算法前提必須是

A. 基本演算法——二分查找演算法

    二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。

1.條件

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

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

2.步奏

（1）首先，假設表中元素是按升序排列，將表中間位置記錄的 關鍵字 與查找關鍵字比較，如果兩者相等，則查找成功；

（2）否則利用中間位置 記錄 將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表；

（3）重復以上過程，直到找到滿足條件的 記錄 ，使查找成功，或直到子表不存在為止，此時查找不成功。

3.舉例

    有一組元素{1，2，3，4，5，6，7，8，9}，如何查到元素為3。

（1）找到數組中中間元素值5，不等於3，所以把數組分為{1，2，3，4}，{5，6，7，8，9}；

（2）因為5大於3，所以3在前一個數組{1，2，3，4}中查找，中間變數2，3比2大，所以在{3，4}中查詢；

（3）查詢到3=3，成功。

4.復雜度

     最好的情況下，1次查詢成功；最壞的情況下，查詢到最後兩個數或者最後也查不到相等數，時間復雜度為O(log2n)。

B. 有序線性表能進行二分查找的前提是該線性表必須是（）存儲的填空

二分查找需要：1.確定元素之間比較大小的運算符
2.排序，3.各元素能夠隨機訪問，也就是給出下標就能訪問指定元素，而不是像鏈表那樣只能順序訪問。這三個條件具備，就可以用二分查找。
由於你已經說了是有序線性表了，那麼就差一個條件，隨機訪問。也就是這個線性表不能是鏈表的形式，而是數組形式

C. python演算法：二分查找

二分查找： 又稱折半查找 ，輸入一個有序的元素列表（必須是有序的）， 將列表中間位置記錄的元素與查找元素比較， 如果查找的元素包含在列表中， 則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的元素大於查找元素，則進一步查找前一子表，否則進一步查找後一子表，重復以上過程，直到找到滿足條件的記錄，使查找成功， 二分查找 返回其位置； 或直到子表不存在為止，此時查找不成功 ，返回None。

二分查找演算法要求 ： .必須是有序列表；

二分查找演算法時間復雜度： O(log n)

二分查找演算法優點： 比較的次數少，查找速度快，平均性能好，佔用系統內存較少。

def binary_search(list,item):

low = 0

high = len(list) - 1

while low <= high:

mid = int((low + high)/2) # 整除計算也可用 mid = (low + high)//2

guess = list[mid]

if guess == item:

return mid

if guess < item:

low = mid + 1

else:

high = mid - 1

return None

my_list = [1,3,5,6,8,7,9,12,18,45]

print (binary_search(my_list,2))

print (binary_search(my_list,12))

D. 二分查找法

二分查找法的解釋如下：

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

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

演算法要求：

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

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

比較次數

計算公式：

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

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

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

E. 二分查找演算法

前提要求數據排好序，有遞歸和非遞歸版本
int binSearch(const int *Array,int start,int end,int key)
{
int left,right;
int mid;
left=start;
right=end;
while (left<=right) { /注釋中為遞歸演算法，執行效率低，不推薦
mid=(left+right)/2;
/* if (key<Array[mid]) {
return(binSearch(Array,left,mid,key));
}
else if(key>Array[mid]){
return (binSearch(Array,mid+1,right,key));
}
else
return mid;
*/
if (key<Array[mid]) {
right=mid-1;
}
else if(key>Array[mid]){
left=mid+1;
}
else
return mid;
}
return -1;
}

F. 二分查找法適用的前提條件其查找的基本思想

適用的前提條件：1. 存儲在數組中（例如一維數組）
2. 數組元素為有序（例如升序）
查找的基本思想：折半查找，設查找的元素為value
value與中間元素（middle = left + (right -left) / 2這樣做的好處防止中間元素出現越界）比較，若比中間值小則查找范圍在middle + 1繼續查找，若比中間值大則查找范圍在middle -1,若與中間值相等則查找結束索引元素為value = middle。

G. 二分搜索演算法的前提條件

只需要在關鍵字上是有序的數組，就可以進行二分查找。

H. 二分查找演算法

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

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

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

I. 二分法查找的適用條件

說」二分查找法只適用於順序存儲的有序表「是正確的，說」指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）「是為了程序的確定性。
實際上只要有序就可以。按遞減排序也可以用二分法。只是必須把演算法規則改變一下。
遞增的演算法：拿要查找數值與中間序號的數值比較若相等，查找成功；要查找數值比中間序號的數值大，在右邊查找，低端序號改為原中間序號加1；要查找數值比中間序號的數值小，在左邊查找，高端序號改為原中間序號減1；如此反復。
遞減的演算法：拿要查找數值與中間序號的數值比較若相等，查找成功；要查找數值比中間序號的數值大，在左邊查找，高端序號改為原中間序號減1；要查找數值比中間序號的數值小，在右邊查找，低端序號改為原中間序號加1；如此反復。

J. 對線性表進行二分法查找的前提條件是什麼

二分查找又稱為折半查找，是一種效率較高的查找方法，其中查找的關鍵是要求線性表是有序表，即表中的元素按關鍵字有序。
例如：
int BinSearch(SeqList R,int n, KeyType k)
{
int low=0, high =n-1,mid;
while(low<=high)
{
mid =(low+high)/2;
if(R[mid].key==k)
return mid+1;
if(R[mid].key>k)
return mid-1;
else
low=mid+1;
}
return 0;
}