脚本宝典收集整理的这篇文章主要介绍了算法-递归与分治政策-二分搜索,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
给定已按非升序排好的n个元素a[0:n-1],在这n个元素中找出一特定元素x。要求算法在最坏情况下的时间效率为 O(LOGn)。
第一行为n值(n<=1000)和x值;第二行为n个整数。
如果找到x,输出x的下标;否则,输出-1
5 2
5 4 3 2 1
3
/*数据按照降序排列,要求用二分法查找元素X 第一行输入n,x的值 第二行输入n个整数 n个整数用什么来存储--数组a[] 设置两个指针,left和right*//*知识回顾二分查找(折半查找):是一种效率较高的查找方法,但要求线性表必须使用顺序存储结构,且表中元素按照关键字有序排列。@R_887_1304@O(log2n).局限性:1.基于顺序表存储结构2.适合一次排序,多次查找。因此针对有序且静态数据。那,在动态数据集合中,如何快速查找数据?考虑树查找3. 数据量小,不需要二分4. 数据量太大也不行
非递归算法1. 设表长为n,low、high和mid分别指向待查元素所在区间的上界、下界和中点, k为给定值。2. 初始时,令:low = 1, high = n, mid = (low+high)/23. 重复以下操作,直至low>high(查找失败): 1)若 k == R[mid].key,查找成功 2)若 k < R[mid].key,则high = mid-1 3)若 k > R[mid].key,则low = mid+1
int SeArch_Bin(SSTable ST, KeyTyPE key){ //若找到,则函数值为该元素在表中的位置,否则为0 low = 1; high = ST.length; while(low <= high)
{ mid = (low+high) / 2; if(key == ST.R[mid].key) return mid; else if(key < ST.R[mid].key) high = mid-1; //前一子表查找 else low = mid + 1; //后一子表查找 } return 0; //表中不存在待查元素}
递归算法int Search_Bin(SSTable ST, keyType key, int low,int high) { if(low>high) return 0; //查找不到时返回0 mid = (low+high) / 2; if(key==ST.elem[mid].key) return mid; else if(key<ST.elem[mid].key) …….. //递归 else ……. //递归}
*/
#include<iostream>using namespace std;
int bsearch(int x,int a[],int left,int right){ if(left>right) //注意终止条件!没有数 return -1; int mid=(left+right)/2; if(x==a[mid]) return mid; if(x<a[mid]) return bsearch(x,a,mid+1,right); else return bsearch(x,a,left,mid-1);}/** 5 4 3 2 1 left mid right x = 2 < a[mid] **/int main(){ int n,x; int a[10]; cin >> n >> x; for(int i=0;i<n;i++) { cin >> a[i]; } cout << bsearch(x,a,0,n-1);}
以上是脚本宝典为你收集整理的算法-递归与分治政策-二分搜索全部内容,希望文章能够帮你解决算法-递归与分治政策-二分搜索所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。