二分法搜尋

二分法搜尋

在計算機科學中，二分搜尋（英語：binary search），也稱折半搜尋（英語：half-interval search）、對數搜尋（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜尋算法。搜尋過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜尋算法每一次比較都使搜尋範圍縮小一半。

基本介紹

  • 中文名：二分法搜尋
  • 外文名：Binary Search
  • 學科：計算機科學
  • 時間複雜度：O(logN)
  • 空間複雜度：O(1)
  • 套用：數據查找
算法簡介,複雜度分析,代碼,

算法簡介

給予一個包含n個帶值元素的數組A或是記錄A0...An−1，使得A0≤ ... ≤An−1，以及目標值T，還有下列用來搜尋T在A中位置的子程式。
  1. 令L為0，R為n− 1。
  2. 如果L>R，則搜尋以失敗告終。
  3. 令m（中間值元素）為(L+R) / 2。
  4. 如果Am<T，令L為m+ 1並回到步驟二。
  5. 如果Am>T，令R為m- 1並回到步驟二。
  6. 當Am=T，搜尋結束；回傳值m。
這個疊代步驟會持續通過兩個變數追蹤搜尋的邊界。有些實際套用會在算法的最後放入相等比較，讓比較循環更快，但平均而言會多一層疊代。

複雜度分析

時間複雜度
折半搜尋每次把搜尋區域減少一半，時間複雜度為
。（n代表集合中元素的個數）
空間複雜度
。雖以遞歸形式定義，但是尾遞歸，可改寫為循環。

代碼

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)          printf("沒找到！\n");     else          printf("找到了，在第%d項里",mid+1);  return 0;}
C
#include<stdio.h>//遞歸算法int recurbinary(int *a, int key, int low, int high){    int mid;    if(low > high)        return -1;    mid = (low + high)/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 ) / 2;    while( left < right && a[mid] != key )    {        if( a[mid] < key ) {            left = mid + 1;        } else if( a[mid] > key ) {            right = mid - 1;        }        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;}
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);    }}
PHP
<?php// 二分法的使用數組必須是有序的，或升序，或降序$arr = array(    1, 3, 5, 7, 9, 13);// 遞歸調用（相比較好理解function bsearch_r($v, $arr, $low, $high){    if ($low > $high) {// 先判斷結束條件        return -1;    }    $i = intval(($high + $low)/2);    if ($arr[$i] > $v){        return bsearch_r($v, $arr, $low, $i-1);// 遞歸    } else if ($arr[$i] < $v){        return bsearch_r($v, $arr, $i+1, $high);    } else {        return  $i;    }}echo bsearch_r(1, $arr, 0, count($arr)-1);// 0echo '<hr/>';echo bsearch_r(14, $arr, 0, count($arr)-1);// -1echo '<hr/>';// while循環function bsearch($v, $arr){    $low = 0;    $high = count($arr)-1;// 使用下標，注意減去1    // 注意凡是使用到while的時候，一定要防備無限循環的時候，注意終止循環的判斷。    while($low <= $high){// 比如$low<=$high，這個等於號必須有。        $i = intval(($high + $low)/2);        if ($arr[$i] > $v){            $high = $i-1;        } else if ($arr[$i] < $v){            $low = $i+1;        } else {            return  $i;        }    }    return -1;// 找不到的時候返回-1}echo bsearch(13, $arr);// 5echo '<hr/>';echo bsearch(14, $arr);// -1
Python
#!/usr/bin/python# -*- coding: utf-8 -*-def BinarySearch(array,t):    low = 0    height = len(array)-1    while low < height:        mid = (low+height)/2        if array[mid] < t:            low = mid + 1        elif array[mid] > t:            height = mid - 1        else:            return array[mid]    return -1if __name__ == "__main__":    print BinarySearch([1,2,3,34,56,57,78,87],57)

熱門詞條

聯絡我們