北京师范大学《数据结构——C语言描述》教学课件：第八章 查找

基于有序顺序表的折半查找递归算法 int BinarySearch( dataList A, Data Type x int low, int high)i int mid =-1 f(low-high i mid=(low+ high)/2, if(A data[]. key < x) mid- Binary Search(A, x, mid +1, high ) else if(A data[ mid. key>X) mid- BinarySearch(A, X, low, mid-1); return mid

int BinarySearch ( dataList A, DataType x, int low, int high ) { int mid = -1; if ( low <= high ) { mid = ( low + high ) / 2; if ( A.data[mid].key < x ) mid = BinarySearch ( A, x, mid +1, high ); else if ( A.data[mid].key > x ) mid = BinarySearch ( A, x, low, mid -1 ); } return mid; } 基于有序顺序表的折半查找递归算法

基于有序顺序表的折半查找迭代算法 int BinarySearch( dataList A, Data Type x)i int high=A n-1, low=0, mid while( low <=high)( mid=( low+ high)/2 if(A data mid. key <x) low= mid +1 /右缩查找区间 else if(A data[mid. key>x) high=mid-1;/缩查找区间 else return mid;∥查找成功 return- 查找失败

int BinarySearch ( dataList A, DataType x ) { int high = A.n-1, low = 0, mid; while ( low <= high ) { mid = ( low + high ) / 2; if ( A.data[mid].key < x ) low = mid + 1; //右缩查找区间 else if ( A.data[mid].key > x ) high = mid - 1; //左缩查找区间 else return mid; //查找成功 } return -1; //查找失败 } 基于有序顺序表的折半查找迭代算法