算法：二分法查找適用於數據量較大時，但是數據需要先排好順序。主要思想是：（設查找的數組區間為array[low, high]）
（1）確定該區間的中間位置K（2）將查找的值T與array[k]比較。若相等，查找成功返回此位置；否則確定新的查找區域，繼續二分查找。區域確定如下：a.array[k]>T 由數組的有序性可知array[k,k+1,……,high]>T;故新的區間為array[low,……，K-1]b.array[k]<T 類似上面查找區間為array[k+1,……，high]。每一次查找與中間值比較，可以確定是否查找成功，不成功當前查找區間將縮小一半，遞歸查找即可。時間複雜度為:O(log2n)。
基本介紹
- 中文名：二分法查找
- 外文名：Binary Search
- 類別：查找算法
- 要求：數組中元素是有順序的
- 主要思想：對序列進行遞歸（或循環查找）
算法,算法複雜度分析,時間複雜度,空間複雜度,java代碼,C代碼,C++代碼,php代碼,Python代碼,
算法
[一維數組，折半查找]
假如有一組數為3，12，24，36，55，68，75，88要查給定的值24.可設三個變數front，mid，end分別指向數據的上界，中間和下界，mid=（front+end）/2.
1.開始令front=0（指向3），end=7（指向88），則mid=3（指向36）。因為a[mid]>x，故應在前半段中查找。
2.令新的end=mid-1=2，而front=0不變，則新的mid=1。此時x>a[mid]，故確定應在後半段中查找。
3.令新的front=mid+1=2，而end=2不變，則新的mid=2，此時a[mid]=x，查找成功。
如果要查找的數不是數列中的數，例如x=25，當第三次判斷時，x>a[mid]，按以上規律，令front=mid+1，即front=3，出現front>end的情況，表示查找不成功。
例：在有序的有N個元素的數組中查找用戶輸進去的數據x。
算法如下：
1.確定查找範圍front=0，end=N-1，計算中項mid=（front+end）/2。
2.若a[mid]=x或front>=end,則結束查找；否則，向下繼續。
3.若a[mid]<x,說明待查找的元素值只可能在比中項元素大的範圍內，則把mid+1的值賦給front，並重新計算mid，轉去執行步驟2；若a[mid]>x，說明待查找的元素值只可能在比中項元素小的範圍內，則把mid-1的值賦給end，並重新計算mid，轉去執行步驟2。
算法複雜度分析
時間複雜度
1.最壞情況查找最後一個元素（或者第一個元素）Master定理T(n)=T(n/2)+O(1)所以T(n)=O(log2n)
2.最好情況查找中間元素O(1)查找的元素即為中間元素（奇數長度數列的正中間，偶數長度數列的中間靠左的元素）
空間複雜度
- S(n)=logn
java代碼
public class BinaryTest{ public static int binary(int[] array, int value) { int low = 0; int high = array.length - 1; while(low <= high) { int middle = (low + high) / 2; if(value == array[middle]) { return middle; } if(value > array[middle]) { low = middle + 1; } if(value < array[middle]) { high = middle - 1; } } return -1; } public static void main(String[] args) { int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int value = binary(a, 9); System.out.println(value); }}C代碼
#include<stdio.h>//遞歸算法int recurbinary(int *a, int key, int low, int high){ int mid; if(low > high) return -1; mid = low + (high-low)/2; if(a[mid] == key) return mid; else if(a[mid] > key) return recurbinary(a,key,low,mid -1); else return recurbinary(a,key,mid + 1,high);}//非遞歸算法int binary( int *a, int key, int n ){ int left = 0, right = n - 1, mid = 0; mid = left + (right - left) / 2; while( left < right && a[mid] != key ) { if( a[mid] < key ) { left = mid + 1; } else if( a[mid] > key ) { right = mid; } mid = ( left + right ) / 2; } if( a[mid] == key ) return mid; return -1;}int main(){ int a[] = {1,2,3,4,5,6,7,8,9,12,13,45,67,89,99,101,111,123,134,565,677}; int b[] = {677,1,7,11,67}; int i; for( i=0; i<sizeof(b)/sizeof(b[0]); i++ ) { //printf( "%d\n", recurbinary(a, b[i],0,sizeof(a)/sizeof(a[0])-1) ); printf( "%d\n", binary( a, b[i], sizeof(a)/sizeof(a[0]))); } return 0;}C++代碼
#include<iostream>#define N 10using namespace std;int main(){ int a[N],front,end,mid,x,i; cout<<"請輸入已排好序的a數組元素:"<<endl; for(i=0;i<N;i++) cin>>a[i]; cout<<"請輸入待查找的數x:"<<endl; cin>>x; front=0; end=N-1; mid=(front+end)/2; while(front<end&&a[mid]!=x) { if(a[mid]<x)front=mid+1; if(a[mid]>x)end=mid-1; mid=(front+end)/2; } if(a[mid]!=x) cout<<"沒找到！"<<endl; else cout<<"找到了，在第"<<mid+1<<"項里"<<endl; return 0;}php代碼
<?phpfunction binarySearch($array, $val) { $count = count($array); $low = 0; $high = $count - 1; while ($low <= $high) { $mid = intval(($low + $high) / 2); if ($array[$mid] == $val) { return $mid; } if ($array[$mid] < $val) { $low = $mid + 1; } else { $high = $mid - 1; } } return false;}Python代碼
mylist = [20,50,22,-22,0,15,222,28,29,99,1999,100823,55,35,5,1,2,3,8,9,55,10239,234234]def lgfind(arr,v): arr = sorted(arr)#排序數組，從小到大 print(arr) start = 0 #變數開始 arrLen = len(arr)-1 #變數結束 while( start <= arrLen ): mid = (start + arrLen) // 2 #變數中間值 print('mid',mid) #如果中間的找到直接返回 if arr[mid] == v: return v #比對大小，看看我們要的結果是在上半段，還是下半段 if arr[mid] > v: arrLen= mid - 1 #結果在上半段 else: start= mid + 1 #結果在下半段 return false #沒有則返回假 have = lgfind(mylist,28)print(have)