一,题目
一个数组是由一个递减数列左移若干位形成的,比如{4,3,2,1,6,5}是由{6,5,4,3,2,1}左移两位形成的,在这种数组中查找某一个数。
二,分析
1)在此序列不断二分的过程中,由于原序列是一个递减序列经过旋转得到的,将它从任何位置分开,都会得到两个序列,
其中一个是递减序列
另一个可以通过一个递减序列通过旋转得到。
2)这样在不断地二分查找时,我们处理的序列子片段要么就是一个旋转后递减序列,要么就是一个纯递减序列,
3)无论是前者还是后者,在继续分成两个片段时,至少有一个纯递减序列(可能两个都是,如果之前的序列片段就是纯递减序列的话)。
4)这样我们可以保证能找到一个片段是纯递减序列(if(data[i]>=data[j]))
5)然后判断我们要找的数是否在这个片段中(这是很直观的,if(data[i]<=num&&num<=data[j])),如果在则继续在此片段中查找,否则说明在另一个序列中,则递归在其中查找
三,源码
#include<iostream>
using namespace std;
int bisearch(int a[],int left,int right,int num)
{
if(a==NULL||right<0)
return -1;
if(left==right)//还剩下一个值的时候
{
if(a[left]==num)
return left;
else
return -1;
}
//int mid=(left+right)/2;
int mid=left+(right-left)/2;
if(a[mid]==num)
return mid;
if(a[mid]<=a[left])//左侧纯递减
{
if(num>a[mid]&&num<=a[left]) //左侧
return bisearch(a,left,mid-1,num);
else
return bisearch(a,mid+1,right,num);
}
else //右侧纯递减
{
if(num>=a[right]&&num<a[mid]) //右侧
return bisearch(a,mid+1,right,num);
else
return bisearch(a,left,mid-1,num);
}
}
int main()
{
int a[100]={4,3,2,1,6,5};
cout<<bisearch(a,0,5,6)<<endl;
return 0;
}
分享到:
相关推荐
48.二分查找 49.二分求根 50.发工资的日子 51.方差 52.分离单词 53.分数拆分 54.分数化小数 55.分数加减法 56.复数 57.高低交换 58.公园喷水器 59.韩信点兵 60.行程编码压缩算法 61.合并字符串 62.猴子分桃 63.火车...
实例025 二分查找 31 实例026 分块查找 32 实例027 哈希查找 34 实例028 斐波那契数列 37 实例029 哥德巴赫猜想 38 实例030 尼科彻斯定理 39 第4章 常用数据类型 41 实例031 数值型常量的使用 42 实例032 字符型变量...
实例213 二分查找法的实现方法 377 实例214 模拟操作系统的进程调度 379 实例215 利用栈将字符串逆序输出 381 实例216 动态的数组链表 382 实例217 你能猜出鱼是谁的宠物吗? 387 实例218 使用...
实例213 二分查找法的实现方法 377 实例214 模拟操作系统的进程调度 379 实例215 利用栈将字符串逆序输出 381 实例216 动态的数组链表 382 实例217 你能猜出鱼是谁的宠物吗? 387 实例218 使用Collections类对List的...
第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置...
实例213 二分查找法的实现方法 377 实例214 模拟操作系统的进程调度 379 实例215 利用栈将字符串逆序输出 381 实例216 动态的数组链表 382 实例217 你能猜出鱼是谁的宠物吗? 387 实例218 使用Collections类对List的...
实例213 二分查找法的实现方法 377 实例214 模拟操作系统的进程调度 379 实例215 利用栈将字符串逆序输出 381 实例216 动态的数组链表 382 实例217 你能猜出鱼是谁的宠物吗? 387 实例218 使用Collections类对...
7.5.2.2 第二阶段 144 7.5.2.3 输入类型 144 7.5.2.4 输出类型 145 7.5.2.5 依赖 145 7.5.2.6 输出类型推断 145 7.5.2.7 参数类型显式推断 145 7.5.2.8 精确推断 145 7.5.2.9 下限推断 145 7.5.2.10 上限推断 146 ...
7.5.2.2 第二阶段 144 7.5.2.3 输入类型 144 7.5.2.4 输出类型 145 7.5.2.5 依赖 145 7.5.2.6 输出类型推断 145 7.5.2.7 参数类型显式推断 145 7.5.2.8 精确推断 145 7.5.2.9 下限推断 145 7.5.2.10 上限推断 146 ...
7.5.2.2 第二阶段 144 7.5.2.3 输入类型 144 7.5.2.4 输出类型 145 7.5.2.5 依赖 145 7.5.2.6 输出类型推断 145 7.5.2.7 参数类型显式推断 145 7.5.2.8 精确推断 145 7.5.2.9 下限推断 145 7.5.2.10 上限推断 146 ...
7.5.2.2 第二阶段 144 7.5.2.3 输入类型 144 7.5.2.4 输出类型 145 7.5.2.5 依赖 145 7.5.2.6 输出类型推断 145 7.5.2.7 参数类型显式推断 145 7.5.2.8 精确推断 145 7.5.2.9 下限推断 145 7.5.2.10 上限推断 146 ...
7.5.2.2 第二阶段 144 7.5.2.3 输入类型 144 7.5.2.4 输出类型 145 7.5.2.5 依赖 145 7.5.2.6 输出类型推断 145 7.5.2.7 参数类型显式推断 145 7.5.2.8 精确推断 145 7.5.2.9 下限推断 145 7.5.2.10 上限推断 146 ...
7.5.2.2 第二阶段 ... 128 7.5.2.3 输入类型 ... 129 7.5.2.4 输出类型 ... 129 7.5.2.5 依赖 ... 129 7.5.2.6 输出类型推断 ... 129 7.5.2.7 参数类型显式推断 ... 129 7.5.2.8 精确推断 ... 129 7.5.2.9 ...
【案例2.1.6】 第48页 2、注意多出口函数的处理 第49页 【案例2.2.1】 第49页 三、维护类代码问题 第51页 1、 统一枚举类型的使用 第51页 【案例3.1.1】 第51页 2、 注释量至少占代码总量的20% 第51页 【案例3.2.1...
98 <br>0154 格式化输入数据为货币格式 99 <br>0155 如何计算两个整数的乘积 99 <br>0156 如何将二进制数转换为十进制数 100 <br>0157 如何将二进制数转换为八进制数 100 <br>0158 如何将二...
1. 简介 ...............................................................................1.8 数组 ..............................................................................................................