编写程序用减治法实现折半查找，要求输入数字，输出其位置。（给出运算结果截图）

秒速五厘米 2021-07-24 20:13 258阅读 0赞

### 题目 ###

编写程序用减治法实现折半查找，要求输入数字，输出其位置。（给出运算结果截图）

**输入格式**

第一行包含整数 n 和 x，表示数组长度和要查询的数。

第二行包含 n 个整数（均在 1∼10000范围内），表示完整数组（该数组为有序递增数组）。

**输出格式**

输出x的具体位置。

**输入样例**

8 5
    1 2 3 4 5 6 7 8

**输出样例**

4

题目保证一定有解。

## 思路 ##

折半查找即二分查找，我们二分查找小于等于x的最大边界。  
![20210417095143101.png][]

### 代码 ###

#include<stdio.h>
    const int N = 10010;
    int a[N];
    int main()
    { 
    	int n,x;
    	scanf("%d%d",&n,&x);
    	for(int i = 0; i < n; i++)
    	{ 
    		scanf("%d",&a[i]);
    	}
    	int l = 0 , r = n - 1;
    	while(l < r)
    	{ 
    		int mid = (l + r + 1)/2;
    		if(a[mid] <= x)  l = mid;
    		else r = mid - 1;
    	}
    	printf("%d\n",l);
    	return 0;
    }

**运行截图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[20210417095143101.png]: /images/20210724/4a81eeec6c584804afc47829d8618bf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/845e0c8f3ea3416fb6404da093caae5b.png

发表评论取消回复

表情：

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

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

相关阅读

相关折半查找--减治法

折半查找–减治法 ‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬

r囧r小猫/ 2024年03月17日 09:53/ 0 赞/ 55 阅读

相关二分查找法（折半查找法）

要求：给定数组必须要是有序的（要么从小到大，要么从大到小排序）。 -------------------- 原理:二分法查找（Binary Search）也称折半查找

╰半夏微凉°/ 2023年06月15日 11:01/ 0 赞/ 14 阅读

相关 c语言折半查找输出坐标,用c语言编写折半查找法

折半查找法又称为二分查找，是在一个有序数组里面找到一个具体的数，方法我在代码里注释到了。 \include int binary\_search(int \arr, int

本是古典何须时尚/ 2023年01月22日 06:53/ 0 赞/ 5 阅读

相关用折半查找法（二分查找），实现查询数组中的元素

折半查找法折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic sear

ゝ一纸荒年。/ 2022年12月23日 06:54/ 0 赞/ 116 阅读

相关减治法之插入排序（C实现）

include <stdio.h> void InsertSort(int A[]); int main() { int i, a

约定不等于承诺〃/ 2022年08月09日 18:51/ 0 赞/ 84 阅读

相关递归法实现折半查找

include <stdio.h> int BinSearch(int a,int low,int high,int key) {

末蓝、/ 2022年07月13日 09:54/ 0 赞/ 193 阅读

相关用java实现折半查找

package service; import java.util.Scanner; public class Test003 {

旧城等待，/ 2022年07月10日 23:47/ 0 赞/ 54 阅读

相关折半查找法

2017年7月20号,天晴对有序序列利用折半查找法查找某元素,若找到,返回找到了,并返回下标值,没找到则返回找不到 \include<stdio.h> int

素颜马尾好姑娘i/ 2022年06月12日 10:11/ 0 赞/ 157 阅读

相关折半查找法

折半查找法: 1. 首先的条件就是该数组是有序的 2. 再次把数组对半拆 3. 然后将查找的数与数组中间的数作比较 4. 比较后有三种情况: (1) 等于

待我称王封你为后i/ 2022年03月17日 01:06/ 0 赞/ 220 阅读

相关编写程序用减治法实现折半查找，要求输入数字，输出其位置。（给出运算结果截图）

题目编写程序用减治法实现折半查找，要求输入数字，输出其位置。（给出运算结果截图）输入格式第一行包含整数 n 和 x，表示数组长度和要查询的数。

秒速五厘米/ 2021年07月24日 20:13/ 0 赞/ 259 阅读