二分查询 基本思路是:如图31所示,设数列为 a12,,an,被查找的数据为x,则查找 首先对am(m=(1+n)2进行,于是得到如下 三种情形: ·若x>am,则x可能在区间[am+1,a门]中 y…·若x<am,则x可能在区间a1,am1中; 若x=am,则以am为所查找数据x,求解结 束
11 二分查询 基本思路是：如图3.1所示，设数列为 a1,a2,…，an，被查找的数据为x，则查找 首先对am(m=(1+n)/2)进行，于是得到如下 三种情形： ·若x>am，则x可能在区间[ am+1,ar]中； ·若x<am，则x可能在区间[a1，am-1]中； ·若x=am，则以am为所查找数据x，求解结 束
二分查找 目的元素 r am am 第1次测试元素 第2次查找区间 第1次查找区间 12
12 二分查找 a1 a2 …… am am- 1 …… an x 第1次查找区间 第2次查找区间 第1次测试元素 目的元素 m S’ r‘ r an
个递归函数 BinSrch(srx m=(s+r)/2 ix=am)打印找到信息后返回; else if(s>=r)打印找不到信息结束程序执行 else if(x>am)调用函数 binsrch(m+1r,x) else 调用函数 binSrch(sm-1x) 13
13 一个递归函数 BinSrch（s,r,x） { m = (s + r)/2; if(x == am) 打印找到信息后返回; else if(s >= r) 打印找不到信息,结束程序执行; else if(x > am) 调用函数binsrch（m + 1,r,x）; else 调用函数binSrch（s,m - 1,x）; }
#include <iostream. h #include <stdlib h class Bin Search private double*Plist public. BinSearch(double int); void Bin Srch(int int, double ) bInsEarch BinSearch. BinSearch( double *list, int ListLong) Plist=new double Listlongl for(int 1=0 i<ListLong: 1++) Plist[]=list[i]: BinSearch:: -Bin Search delete [Plist
14 #include <iostream.h> #include <stdlib.h> class BinSearch { private: double *Plist; public: BinSearch(double *,int); void BinSrch(int ,int ,double ); ~BinSearch(); }; BinSearch:: BinSearch(double *list,int ListLong) { Plist=new double[ListLong]; for(int i=0;i<ListLong;i++) Plist[i]=list[i]; } BinSearch::~BinSearch() { delete []Plist; }
void BinSearch: BinSrch(int s, int r, double x) if( Plist[m==x) cout<< The order of"<<x<<" is"<<m+l <<" in this sequence. else if(s >=r) cout <<x<<"is not exist in the seguense t(-1) else if(x> Plist(m) BinSrch(m 1, r, x) ∥递归调用 BinSrch(s, m ∥递归调用 void maino double al{1.1,1.3,1,5,1.7,1.9,2.1,2.3,2.5,2.7,2.9}; ∥数组(模拟表)声明及初始化 double x= 2.3 BinSearch bs(a, 10) 对象声明及初始化 bs BinSrch(s, r, x) ∥调用成员函数 15
15 void BinSearch::BinSrch(int s,int r,double x) { int m; m = (s + r)/2; if(Plist[m] == x) { cout << "The order of" << x << "is" << m+1 << "in this sequence."; return; } else if(s >= r) { cout << x <<"is not exist in the seguense."; exit(-1); } else if(x > Plist[m]) BinSrch(m + 1, r, x); // 递归调用 else BinSrch(s, m - 1, x); // 递归调用 } void main() { double a[]={1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9}; // 数组（模拟表）声明及初始化 double x = 2.3; int s = 0, r = 9; BinSearch bs(a,10); //对象声明及初始化 bs.BinSrch(s,r,x); //调用成员函数 }