二分查找知多少？

我就是我 2021-11-19 14:46 360阅读 0赞

1，给定一个有序（不降序）数组arr，求任意一个i使得arr\[i\]等于v，不存在则返回-1。

2，给定一个有序（不降序）数组arr，求最小的i使得arr\[i\]等于v，不存在则返回-1。

3，给定一个有序（不降序）数组arr，求最大的i使得arr\[i\]等于v，不存在则返回-1。

4，给定一个有序（不降序）数组arr，求最大的i使得arr\[i\]小于v，不存在则返回-1。

5，给定一个有序（不降序）数组arr，求最小i使得arr\[i\]大于v，不存在则返回-1。

解答：我们一个个来解决，第一个问题相对简单，但要注意边界条件，代码如下：

//二分查找在字符串数组arr中找到任意一个i，使得arr\[i\]=v，不存在则返回-1，

//1,递归版本

int BS(char \*\*arr,char \*v,int i,int j)\{

if(i>=j)\{

if(!strcmp(arr\[i\],v))\{

return i;

\}

else

return -1;

\}

int mid=i+(j-i)/2;    //注意不能写成mid=(i+j)/2，容易产生加法溢出

if(!strcmp(arr\[mid\],v))

return mid;

else if(strcmp(arr\[mid\],v)>0)

return BS(arr,v,i,mid-1);

else

return BS(arr,v,mid+1,j);

\}

第二个问题，只要改变一下在与中间值相同的时候，状态转移函数发生变化

//二分查找在字符串数组arr中寻找最小的i，使得arr\[i\]=v，不存在则返回-1，

//递归版本

int BS\_min(char \*\*arr,char \*v,int i,int j)\{

if(i>=j)\{

if(!strcmp(arr\[j\],v))\{  //注意这里也有所不同

return j;

\}

else

return -1;

\}

int mid=i+(j-i)/2;

if(!strcmp(arr\[mid\],v))//相等，继续在左边找，注意下标是mid而不是mid-1

return BS\_min(arr,v,i,mid);

else if(strcmp(arr\[mid\],v)>0)

return BS\_min(arr,v,i,mid-1);

else

return BS\_min(arr,v,mid+1,j);

\}

第三个问题和第二个问题类似：

//二分查找在字符串数组arr中寻找最大的i，使得arr\[i\]=v，不存在则返回-1，

//递归版本

int BS\_max(char \*\*arr,char \*v,int i,int j)\{

if(i>=j || i==j-1)\{//如果不加i==j-1，程序可能会进入死循环

if(!strcmp(arr\[j\],v))\{

return j;

\}

else if(!strcmp(arr\[i\],v))\{

return i;

\}

else

return -1;

\}

int mid=i+(j-i)/2;

if(!strcmp(arr\[mid\],v))//相等，继续在右边找，注意下标是mid而不是mid+1

return BS\_max(arr,v,mid,j);

else if(strcmp(arr\[mid\],v)>0)

return BS\_max(arr,v,i,mid-1);

else

return BS\_max(arr,v,mid+1,j);

\}

第四题稍微有点难度

转载于:https://www.cnblogs.com/kevinLee-xjtu/archive/2011/12/21/2299081.html

发表评论取消回复

表情：

评论列表（有 0 条评论，360人围观）

还没有评论，来说两句吧...

相关阅读

相关 jsp知多少？

一、jsp介绍 JSP(全称Java Server Pages)是由Sun 公司专门为了解决动态生成HTML文档的技术。 jsp页面的访问千万不能像HTML页面一样。托

旧城等待，/ 2022年12月10日 07:29/ 0 赞/ 248 阅读

相关 servlet知多少？

一、什么是Servlet 1 Servlet是JavaEE规范之一.它是JavaWeb的三大组件之一.JavaWeb的三大组件分别是:Servlet程序,Filter过滤器

约定不等于承诺〃/ 2022年12月10日 07:27/ 0 赞/ 185 阅读

相关 Session知多少？

一、什么是session？ ①：Session是一个接口,类名是HttpSession. ②：Session是一个域对象( 域对象是可以像map一样存取数据的对象,域是

左手的ㄟ右手/ 2022年11月30日 12:38/ 0 赞/ 220 阅读

相关 Cookie知多少？

一、什么是cookie？ ①：Cookie翻译过来是饼干. ②：Cookie是服务器通知客户端保存键值对的一种技术. ③：每个 Cookie的大小不能超过4kb

一时失言乱红尘/ 2022年11月30日 12:38/ 0 赞/ 208 阅读

相关 Sprintf知多少

Sprintf知多少在将各种类型的数据构造成字符串时，sprintf 的强大功能很少会让你失望。由于sprintf 跟printf 在用法上几乎一样，只是打印的目的地不同而

野性酷女/ 2022年08月24日 06:08/ 0 赞/ 240 阅读

相关 SEO知多少

在这个互联网的大时代，网络营销成了一个巨大市场，很多企业都拥有了自己网站，然而网站必须要推广，搜索引擎是最好的推广方式。这就用到了这门学问了。 SEO(Search Eng

爱被打了一巴掌/ 2022年08月04日 16:48/ 0 赞/ 251 阅读

相关 sizeof 知多少?

稍熟悉C/C++的朋友,对于sizeof肯定不陌生,通过他我们可以知晓某个类型或者实例的内存大小(以字节计),但是如果深入一下sizeof计算的细节,想来大部分朋友就不会那么熟

雨点打透心脏的1/2处/ 2022年06月08日 08:07/ 0 赞/ 270 阅读

相关查找——二分查找

基本思想二分查找是建立在有序顺序表基础上的！步骤如下： 1. 将表中间位置记录的关键字与给定K值进行比较，若两者相等，则查找成功。 2.

蔚落/ 2022年03月27日 03:46/ 0 赞/ 373 阅读

相关进程知多少？

![e0e9132bf71b4e72b1269e23adf257e0_0063_01.jpg][] 要讲线程，一般都得讲一讲进程，进程是何方神圣呢？下面来简单介绍一下。先

梦里梦外;/ 2021年12月10日 05:43/ 0 赞/ 661 阅读

相关二分查找知多少？

1，给定一个有序（不降序）数组arr，求任意一个i使得arr\[i\]等于v，不存在则返回-1。 2，给定一个有序（不降序）数组arr，求最小的i使得arr\[i\]等于v，

我就是我/ 2021年11月19日 14:46/ 0 赞/ 361 阅读