折半查找
在10000個10000以內增序數列中，查找用戶輸入的0到9999范圍的任意數，找到的輸出數字的位置，找不到則回傳-1.
c++語言撰寫下代碼
uj5u.com熱心網友回復：
作業自己做去uj5u.com熱心網友回復：
貌似是資料結構，這種很好做呀。uj5u.com熱心網友回復：
//-----------------------------------------------------------------------------------------------///二分查找陣列指定元素的下標
/**
要求陣列是一個有序的陣列,并和Compare對應用的上
@param [in] paramArray 要查找的陣列
@param [in] paramElement 要查找的元素
@param [in] paramEqual 比較兩個元素是否相等的物件
@return 回傳查找結果
- ARRAY_INVALID_INDEX 表示資料未找到
- 其它值 表示資料在陣列中的下標
*/
template<class Array,class E,class Compare>
XInt Array_Find_Binary(const Array & paramArray, const E & paramElement, const Compare & paramCompare)
{
XInt Low = paramArray.getFirstIndex();
XInt High = paramArray.getLastIndex();
XInt Mid;
XInt iRet = ARRAY_INVALID_INDEX;
while( Low <= High )
{
Mid = (Low + High) /2;
const typename Array::ElementType & Tmp = paramArray[Mid];
XInt CompareResult = paramCompare(Tmp, paramElement);
if( CompareResult == 0 )
{
iRet = Mid;
break;
}
else if( CompareResult > 0 ) High = Mid -1;
else Low = Mid + 1;
}
return iRet;
}
這是我好多年前寫的，這個是于陣列的
uj5u.com熱心網友回復：
好好學習，才能天天向上。/* 有序表上的二分查找
基本思想：在一個查找區間中，確定出查找區間的中心位置，用待查找數
據元素的關鍵字和中心位置上資料元素的關鍵字比較，若兩者相等則查找成
功;否則若前者小于后者，則把區間定為原查找區間的前半段，繼續這樣的
程序;否則若前者大于后者，則把查找的區間定為原查找區間的后半段，繼
續這樣的程序.這樣的查找程序一直進行到查找區間的上界小于查找區間的下
界為止.由于二分查找演算法每次比較后都把查找區間折半，所以該演算法也稱做
折半查找演算法.
回圈結構的二分查找
#include <iostream>
using namespace std;
int BiSearch(int a[],int n,int key);
void main()
{
int z;
int a[10]={0,1,2,3,4,5,6,7,8,9};
z=BiSearch(a,10,4);
cout<<z<<endl;
}
int BiSearch(int a[],int n,int key)
在有序表a[0]--a[n-1]中二分查找關鍵碼為key的資料元素，查找成功時
回傳該元素的下標序號;失敗時回傳-1
{
int low=0,high=n-1;
int mid;
while (low<=high)
{
mid=(low+high)/2; 確定查找區間*
if(a[mid]==key)return mid; 查找成功
else if(a[mid]<key)low=mid+1;
else high=mid-1;
}
return -1; 查找失敗
}
/* 遞回結構的二分查找 */
#include <iostream>
using namespace std;
int BSearch(int a[],int x,int low,int high);
void main()
{
int a[]={1,3,4,5,17,18,31,33};
int x=4;
int bn;
bn=BSearch(a,x,0,7);
if (bn==-1)cout<<"x不在陣列a中!"<<endl;
else
cout<<"x在陣列a的下標是:"<<bn<<endl;
}
int BSearch(int a[],int x,int low,int high)
{
int mid;
if(low>high)return -1; //查找不成功
mid=(low+high)/2;
if(x==a[mid])return mid; //查找成功
else if(x<a[mid])
return BSearch(a,x,low,mid-1); //在下半區查找
else
return BSearch(a,x,mid+1,high); //在上半區查找
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/107078.html
標籤：基礎類
上一篇：求助 c++ builder 運行了之后 視窗關不掉 關機都關不掉
下一篇：modbus