递归-PTA改写二分搜索算法

Bertha 。 2022-12-22 11:22 119阅读 0赞

题目来源：《计算机算法设计与分析》，王晓东

设a\[0:n-1\]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

输入格式:  
输入有两行：

第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。

输出格式:  
输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中时，i和j相同。 提示：若x小于全部数值，则输出：-1 0 若x大于全部数值，则输出：n-1的值 n的值

输入样例:  
在这里给出一组输入。例如：

6 5  
2 4 6 8 10 12  
输出样例:  
在这里给出相应的输出。例如：

1 2

#include<stdio.h>
    int search(int x,int a[],int left,int right){
        
          int center=(left+right)/2;
    	  if(a[center-1]<x && x<a[center])
    		  printf("%d %d\n",center-1,center);
    	  else if(left<=right){
        
    	  if(x==a[center])
    		  printf("%d %d\n",center,center);
    	  else if(x<a[center])
    		  search(x,a,left,center-1);
    	  else if(x>a[center])
    		  search(x,a,center+1,right);
    	  }
    	  return 0;
    }
    int main(){
        
        int n,x;
    	int a[1000];
    	scanf("%d %d",&n,&x);
    	for(int i=0;i<n;i++){
        
    	    scanf("%d",&a[i]);
    	}
    	if(x<a[0])
    		printf("-1 0\n");
    	else if(x>a[n-1])
    		printf("%d %d\n",n-1,n);
    	else search(x,a,0,n-1);
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关二分查找算法(非递归)

1.二分查找算法(非递归)介绍 1. 前面我们讲过了二分查找算法，是使用递归的方式，下面我们讲解二分查找算法的非递归方式 2. 二分查找法只适用于从有序的数列中进行查找(

古城微笑少年丶/ 2024年03月27日 01:49/ 0 赞/ 53 阅读

相关递归-PTA改写二分搜索算法

题目来源：《计算机算法设计与分析》，王晓东设a\[0:n-1\]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置

Bertha 。/ 2022年12月22日 11:22/ 0 赞/ 120 阅读

相关递归-PTA二分查找

输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。输

「爱情、让人受尽委屈。」/ 2022年12月22日 11:22/ 0 赞/ 136 阅读

相关二分查找的非递归与递归算法

一.引入: 假设一个已经\[排好序的数组a\[n\] ,若要搜索其中某个元素x,一般想到的是逐个查找,倘若x刚好在a\[n\],则最坏的情况需要n次比较,如若x不在数组a中,

电玩女神/ 2022年08月18日 12:21/ 0 赞/ 201 阅读

相关二分查找（非递归算法和递归算法）

非递归算法： package mytest; public class test { public static int Bina

水深无声/ 2022年05月29日 06:17/ 0 赞/ 201 阅读

相关二分查找算法递归实现

/ Created by panjiannan on 2018/7/3. / public class BinarySearch { pub

桃扇骨/ 2022年05月21日 07:52/ 0 赞/ 189 阅读

相关递归——线性递归与二分递归

递归线性递归例子1：数组求和 int sum( int A[], int n) { //数组求和算法：线性递归版 if

向右看齐/ 2022年05月21日 04:41/ 0 赞/ 296 阅读

相关二分查找的递归算法

二分查找的递归算法 -------------------- 算法名称:find 算法功能：　　在n个整数的有序数组a中找x

电玩女神/ 2022年01月06日 08:29/ 0 赞/ 214 阅读

相关 Java递归实现二分搜索树

导读: 本文分为两部分: 1.实现代码 2.测试代码实现代码如下: private class Node{ public E e;

淩亂°似流年/ 2021年12月23日 07:11/ 0 赞/ 244 阅读

相关二分查找非递归算法

一算法说明 1 二分查找可以使用递归的方式，也可以使用非递归的方式。 2 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找。 3

浅浅的花香味﹌/ 2021年07月25日 00:00/ 0 赞/ 361 阅读