-
二分查找
鎖定
- 中文名
- 二分查找
- 外文名
- Binary Search
- 別 名
- 折半查找
- 提出者
- John Mauchly
- 提出時間
- 1946年
二分查找查找過程
首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與查找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。重複以上過程,直到找到滿足條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。
二分查找算法要求
1.必須採用順序存儲結構。
2.必須按關鍵字大小有序排列。
二分查找比較次數
計算公式:
當順序表有n個關鍵字時:
查找失敗時,至少比較a次關鍵字;查找成功時,最多比較關鍵字次數是b。
注意:a,b,n均為正整數。
二分查找算法複雜度
二分查找的基本思想是將n個元素分成大致相等的兩部分,取a[n/2]與x做比較,如果x=a[n/2],則找到x,算法中止;如果x<a[n/2],則只要在數組a的左半部分繼續搜索x,如果x>a[n/2],則只要在數組a的右半部搜索x.
時間複雜度即是while循環的次數。
總共有n個元素,
漸漸跟下去就是n,n/2,n/4,....n/2^k(接下來操作元素的剩餘個數),其中k就是循環的次數
由於你n/2^k取整後>=1
即令n/2^k=1
可得k=log2n,(是以2為底,n的對數)
所以時間複雜度可以表示O(h)=O(log2n)
下面提供一段二分查找實現的偽代碼:
BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max
折半查找法也稱為二分查找法,它充分利用了元素間的次序關係,採用分治策略,可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是:(這裏假設數組元素呈升序排列)將n個元素分成個數大致相同的兩半,取a[n/2]與欲查找的x作比較,如果x=a[n/2]則找到x,算法終止;如 果x<a[n/2],則我們只要在數組a的左半部繼續搜索x;如果x>a[n/2],則我們只要在數組a的右 半部繼續搜索x。
二分查找代碼示例
C#代碼
public static int Method(int[] nums, int low, int high, int target) { while (low <= high) { int middle = (low + high) / 2; if (target == nums[middle]) { return middle; } else if (target > nums[middle]) { low = middle + 1; } else if (target < nums[middle]) { high = middle - 1; } } return -1; }
Go源代碼
func binarySearch(checkSlice []int, findVal int) int { pos := -1 left, right := 0, len(checkSlice) //此處right長度不減1 , 如果最大值為查找值,此處減一代碼進入死循環 Loop: for { if(left >= right){ break Loop } mid := (left + right) / 2 switch true { case checkSlice[mid] < findVal : left = mid case checkSlice[mid] == findVal : pos = mid break Loop case checkSlice[mid] > findVal : right = mid } } return pos }
Go源代碼修正
func BinarySearch(n []int, target int) int { length := len(n) low := 0 high := length - 1 for low <= high { mid := (low + high) / 2 if n[mid] > target { high = mid - 1 } else if n[mid] < target { low = mid + 1 } else { return mid } } return -1 }
Swift源代碼
func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? { var lowerBound = 0 var upperBound = a.count while lowerBound < upperBound { let midIndex = lowerBound + (upperBound - lowerBound) / 2 if a[midIndex] == key { return midIndex } else if a[midIndex] < key { lowerBound = midIndex + 1 } else { upperBound = midIndex } } return nil }
Python源代碼
def bin_search(data_list, val): low = 0 # 最小數下標 high = len(data_list) - 1 # 最大數下標 while low <= high: mid = (low + high) // 2 # 中間數下標 if data_list[mid] == val: # 如果中間數下標等於val, 返回 return mid elif data_list[mid] > val: # 如果val在中間數左邊, 移動high下標 high = mid - 1 else: # 如果val在中間數右邊, 移動low下標 low = mid + 1 return # val不存在, 返回None ret = bin_search(list(range(1, 10)), 3) print(ret)
pascal源代碼
第一種
programjjzx(input,output); var a:array[1..10]ofinteger; i,j,n,x:integer; begin ['輸入10個從小到大的數:'] for i:=1 to 10 do read(a[i]); ['輸入要查找的數:'] readln(x); i:=1;n:=10;j:=trunc((i+n)/2); repeat if a[j]>x then begin n:=j-1;j:=trunc((i+n)/2) end else if a[j]<x then begin i:=j+1;j:=trunc((i+n)/2) end; until(a[j]=x)or(i>=n);{為什麼是這個結束循環條件——i>n表示所查找的範圍已經空了(就是沒找到)} if a[j]=x then writeln('查找成功!位置是:',j:3) else writeln('查找失敗,數組中無此元素!') end.
第二種
var a:array[1..100001] of longint; n,m,i,t:longint; function search(k:longint):longint; var l,r,mid:longint; begin l:=1; r:=n; mid:=(l+r) div 2; while (a[mid]<>k) and (l<=r) do begin if a[mid]>k then r:=mid-1 else l:=mid+1; mid:=(l+r) div 2; end; if l>r then exit(0); exit(mid); end; begin readln(n,m); for i:=1 to n do read(a[i]); for i:=1 to n do begin read(t); if search(t)=0 then writeln('no') else writeln(search(t)); end; end.
C和C++代碼
<C和C++的語法基本相同>
第一種
int BinSearch(SeqList *R,int n,KeyType K) { //在有序表R[0..n-1]中進行二分查找,成功時返回結點的位置,失敗時返回-1 int low=0,high=n-1,mid; //置當前查找區間上、下界的初值 while(low<high) { if(R[low].key==K) return low; if(R[high].key==k) return high; //當前查找區間R[low..high]非空 mid=low+(high-low)/2; /*使用(low+high)/2會有整數溢出的問題 (問題會出現在當low+high的結果大於表達式結果類型所能表示的最大值時, 這樣,產生溢出後再/2是不會產生正確結果的,而low+((high-low)/2) 不存在這個問題*/ if(R[mid].key==K) return mid; //查找成功返回 if(R[mid].key<K) low=mid+1; //繼續在R[mid+1..high]中查找 else high=mid-1; //繼續在R[low..mid-1]中查找 } if(low>=high) return -1;//當low>high時表示所查找區間內沒有結果,查找失敗 }
第二種
int bsearchWithoutRecursion(int array[],int low,int high,int target) { while(low<=high) { int mid=low+(high-low)/2;//還是溢出問題 if(array[mid]>target) high=mid-1; else if(array[mid]<target) low=mid+1; else return mid; } return-1; }
第三種
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-left)/2;//還是溢出問題 if(key==Array[mid]) return mid; else if(key<Array[mid]) right=mid-1; else if(key>Array[mid]) left=mid+1; } return -1; }
function binarySearch(arr,target){ if(!arr.length) return -1;// 考慮邊界值 if(arr.length == 1)return 0;//只有一位無需進入循環 let start = 0; let end = arr.length-1; while(start <= end){ let mid = Math.floor((start + end) / 2);//取中位數,可能除不盡向下取整 if(arr[mid] === target){ return mid; }else if(target > arr[mid]){// 若目標值大於中位值 start = mid +1 //則説明目標值在更右側,將初始下標右移至中位數右側,再次循環 }else{// 若目標值小於中位值 end = mid -1 //則説明目標值在更左側,將結束下標左移至中位數左側,再次循環 } } return -1 }
遞歸實現(可直接編譯)
#include<iostream> using namespace std; int a[100]={1,2,3,5,12,12,12,15,29,55};//數組中的數(由小到大) int k;//要找的數字 int found(int x,int y) { int m=x+(y-x)/2; if(x>y)//查找完畢沒有找到答案,返回-1 return -1; else { if(a[m]==k) return m;//找到!返回位置. else if(a[m]>k) return found(x,m-1);//找左邊 else return found(m+1,y);//找右邊 } } int main() { cin>>k;//輸入要找的數字c語言把cin換為scanf即可 cout<<found(0,9);//從數組a[0]到a[9]c語言把cout換為printf即可 return 0; }
Java代碼
public static int binarySearch(Integer[] srcArray, int des) { //定義初始最小、最大索引 int start = 0; int end = srcArray.length - 1; //確保不會出現重複查找,越界 while (start <= end) { //計算出中間索引值 int middle = (end + start)>>>1 ;//防止溢出 if (des == srcArray[middle]) { return middle; //判斷下限 } else if (des < srcArray[middle]) { end = middle - 1; //判斷上限 } else { start = middle + 1; } } //若沒有,則返回-1 return -1; }
AAuto代碼
//二分查找 functionbinSearch(t,v){ varp=#t; varp2; varb=0; do{ p2=p; p=b+math.floor((p-b)/2)//二分折半運算 if(p==b)return; if(t[p]<v){//判斷下限 b=p; p=p2; } }while(t[p]>v)//判斷上限 returnt[p]==v&&p; } //測試 tab={} //創建數組,每個元素都是隨機數 for(i=1;10;1){ tab[i]=math.random(1,10000) } //插入一個已知數 table.push(tab,5632) //排序 table.sort(tab) io.open() io.print("數組",table.tostring(tab)) io.print("使用二分查找,找到5632在位置:",binSearch(tab,5632)) }
PHP代碼
function binsearch($x,$a){ $c=count($a); $lower=0; $high=$c-1; while($lower<=$high){ $middle=intval(($lower+$high)/2); if($a[$middle]>$x){ $high=$middle-1; } elseif($a[$middle]<$x){ $lower=$middle+1; } else{ return $middle; } } return -1; }
AS3代碼
publicstaticfunctionbinSearch(list:Array,low:int,high:int,key:int):int{ if(low>high) return-1; varmid:int=low+int((high-low)/2); varindex:int=-1 if(list[mid]==key){ index=mid; }elseif(list[mid]<key){ low=mid+1; index=binSearch(list,low,high,key); }else{ high=mid-1; index=binSearch(list,low,high,key); }returnindex; }
JavaScript代碼
var Arr = [3, 5, 6, 7, 9, 12, 15]; function binary(find, arr, low, high) { if (low <= high) { if (arr[low] == find) { return low; } if (arr[high] == find) { return high; } var mid = Math.ceil((high + low) / 2); if (arr[mid] == find) { return mid; } else if (arr[mid] > find) { return binary(find, arr, low, mid - 1); } else { return binary(find, arr, mid + 1, high); } } return -1; } binary(15, Arr, 0, Arr.length - 1);
PHP代碼
/*二分查找:前提,該數組已經是一個有序數組,必須先排序,再查找。*/ function binarySearch(&$array,$findVal,$leftIndex,$rightIndex){ $middleIndex=round(($rightIndex+$leftIndex)/2); if($leftIndex>$rightIndex){ echo'查無此數<br/>'; return; } if($findVal>$array[$middleIndex]){ binarySearch($array,$findVal,$middleIndex+1,$rightIndex); }elseif($findVal<$array[$middleIndex]){ binarySearch($array,$findVal,$leftIndex,$middleIndex-1); }else{ echo"找到數據:index=$middleIndex;value=$array[$middleIndex]<br/>"; if($array[$middleIndex+1]==$array[$middleIndex]&&$leftIndex<$rightIndex){ binarySearch($array,$findVal,$middleIndex+1,$rightIndex); } if($array[$middleIndex-1]==$array[$middleIndex]&&$leftIndex<$rightIndex){ binarySearch($array,$findVal,$leftIndex,$middleIndex-1); } } }