歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

二分查找算法

二分查找又稱折半查找,優點是比較次數少,查找速度快,平均性能好;其缺點是要求待查表為有序表,且插入刪除困難。因此,折半查找方法適用於不經常變動而查找頻繁的有序列表。首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與查找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。重復以上過程,直到找到滿足條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。

Golang二分查找算法的簡單實現 http://www.linuxidc.com/Linux/2014-02/96093.htm

二分查找改進版 http://www.linuxidc.com/Linux/2013-10/91721.htm

二分查找的實現及注意事項 http://www.linuxidc.com/Linux/2013-07/87308.htm

用Python實現二分查找 http://www.linuxidc.com/Linux/2012-12/75948.htm

二分查找之Java實現 http://www.linuxidc.com/Linux/2012-05/59869.htm

Java針對數組的普通查找法和二分查找法 http://www.linuxidc.com/Linux/2012-03/57065.htm

算法要求:

1.必須采用順序存儲結構

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

下面是c++與java的不同實現:

已經假設所查詢數組均為升序排列好了:

C++版:

#include <iostream>
#include <stdlib.h>
#define  ERROR -1
#define LEN 10
using namespace std;
/************************************************************************/
/*  T  自定義數據類型
 value 查找的值
 low  左側邊界 (一般為0)
 high    右側邊界(一般為數組長度-1)
/************************************************************************/
template <class T>
int binarySearch(T table[],T value,int low,int hign){
 if(low<=hign){//邊界有效
  int mid = (low+hign)/2; //找到中間點
  if(table[mid]==value){//如果中間點的值就是我們查找的值,則返回該點
   return mid;
  }else if(table[mid]>value){//如果中間值比查找值大,則證明查找的值在中間點的左側
   return binarySearch(table,value,low,mid-1);//繼續將范圍縮小到原來一半(靠左縮小)
  }else{
   return binarySearch(table,value,mid+1,hign);//繼續將范圍縮小到原來一半(靠右縮小)
  }
 }
 return ERROR;
}
/************************************************************************/
/* 由上述代碼可以知道,上邊界和和下邊界其實就是數組的開始和結束位置,因此上述函數可以泛化為下列函數                                                                    */
/************************************************************************/
template <class T>
int binarySearch(T table[],int n,T value){
 return binarySearch(table,value,0,n-1);
}
template <class T>
void print(T table[],int n){
 for (int i=0;i<n;i++)
 {
  cout<<table[i]<<" ";
 }
 cout<<"\n";
}
int main(void){

 //給出一個已經排序好的數組
 int array[LEN] = {0};
 for (int i=0;i<LEN;i++)
 {
  array[i] = i+10;
 }
 cout<<"您要查找的序列為:";
 print(array,LEN);
 cout<<"請輸入你要查找的內容:";
 int search;
 cin>>search;
 //調用函數
 int searchResult = binarySearch(array,LEN,search);
 cout<<"查找內容為"<<search<<"在指定數組的第"<<(searchResult+1)<<"處"<<endl;
 system("pause");
 return 1;
}

Copyright © Linux教程網 All Rights Reserved