算法-递归与分治政策-二分搜索

发布时间:2022-07-05 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了算法-递归与分治政策-二分搜索脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
7-1 二分搜索(分治法)
 

给定已按非升序排好的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,请注明来意。