二分查找递归

叶茂林

发布于 2023-07-28 21:22:00

4430

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

碎碎念念

假设我们要在一个升序排序的整型数组中查找某个特定的整数，如果找到了，返回该整数在数组中的索引号，如果没有找到，则返回-1。

我们首先看要找的数和数组中间的数的大小关系，如果相等，那么说明找到了，如果要找的数小于数组中间的数，那么我们再在数组的前半部分继续查找，如果大于，那么我们再在数组的后半部分继续查找，每次查找都将范围缩小一半，称为二分查找。

代码

#include<stdio.h>
int binary_search(int line[],int target,int begin,int end)
{
	int middle=(begin+end)/2;
	if(begin>end)
	return -1;
	if(target==line[middle])
	return middle;
	else if(target<line[middle])
	return binary_search(line,target,begin,middle-1);
	return binary_search(line,target,middle+1,end);
}
int main()
{
	int line[10]={1,2,3,4,5,6,7,8,9,10};
	if(binary_search(line,5,0,9)!=-1)
	printf("YES %d",binary_search(line,5,0,9)+1);
	else
	printf("NO");
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-03-03，如有侵权请联系 cloudcommunity@tencent.com 删除

int