二分查找(二分法查找數據)

二分查找

二分法查找數據一般指本詞條

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

基本介紹

  • 中文名:二分查找
  • 外文名:Binary Search
  • 別名:折半查找
  • 提出者:John Mauchly
  • 提出時間:1946年
  • 適用領域:程式語言
  • 套用學科:計算機
  • 優點:查找速度快
  • 缺點:待查表為有序表
  • 時間複雜度:O(log2n) 
查找過程,算法要求,比較次數,算法複雜度,代碼示例,

查找過程

首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與查找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。重複以上過程,直到找到滿足條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功

算法要求

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);
        }
    }
}

熱門詞條

聯絡我們