R语言 Hadoop node.js 二叉树排序 aircrack-ng svn gitee 状态模式 bluetooth LimeJS 网页后台模板 nginx视频 android项目开发 oracle删除字段sql java运行软件 html好看的字体样式 bootstrap文本框 matlab区分大小写吗 python开发环境 python服务器开发 java编程 java时间转换 php实例代码 javascript源代码 圣剑世界 0x0000004e 网络电视软件下载 摩斯电码翻译器 主板芯片组天梯图 魔兽改图工具 JScodeblocks汉化包 文字转语音软件免费版 国都证券官网下载 pp安卓助手 例外被抛出且未被接住 组合索引 win10工作组 total同级生2下载 冲击波专杀 工行天天益
当前位置: 首页 > 学习教程  > 编程语言

二分查找一(简单的递归与非递归实现)

2020/8/31 12:17:01 文章标签:

#include<stdio.h>

#define N 1000

// 二分查找的循环实现
int Binary_search1(int *a, int n, int value)
{
	int low = 0;  // 定义开始下标
	int high = n - 1;  // 定义末尾下标

	while (low <= high)  // 注意循环退出条件是low <= high,不是low < high
	{
		int mid = (low + high) / 2;  // 定义中间位置下标
		if (a[mid] < value)
		{
			// 如果中间元素小于待查找值,说明要找的元素在后方
			low = mid + 1;  
		}
		else if (a[mid] > value)
		{
			// 如果中间元素大于待查找值,说明要找的元素在前方
			high = mid - 1;
		}
		else
		{
			// 如果中间元素正好等于待查找值,则返回中间元素的下标
			return mid;
		}
	}

	return -1;  // 如果找不到值,则返回-1
}

int Binary_search2(int* a, int n, int value)
{
	return bsearchInternally(a, 0, n - 1, value);
}

int bsearchInternally(int* a, int low, int high, int value)
{
	if (low > high) return -1;
	int mid = low + ((high - low) >> 1);  // ">> 1"相当于除以2
	if (a[mid] == value)
	{
		return mid;
	}
	else if (a[mid] < value)
	{
		return bsearchInternally(a, mid + 1, high, value);
	}
	else
	{
		return bsearchInternally(a, low, mid - 1, value);
	}
}

/*
	以上查找需要注意的三个问题:
	1、循环退出条件:low <= high
	2、mid的取值
	3、low和high的更新
*/

int main()
{
	int a[N], data;
	for (int i = 0; i < N; ++i)
	{
		a[i] = i;
	}
	printf("请输入您要查找的数据:");
	scanf("%d", &data);
	int val = Binary_search2(a, N, data);
	printf("您要查找的数在数组a中的第%d个位置", val);
	return 0;
}

/*
	二分查找的局限性:
	1.二分查找依赖的是顺序表结构,即数组
		二分查找不能使用在链表中
	2.二分查找针对的是有序数据
		如果数据没有排序则需要先排序才能使用二分查找
	3.数据量太小不适合二分查找
		如果要处理的数据量很小,就完全没有必要使用二分查找了,循环遍历就够了
	4.数据量太大不适合二分查找
		因为二分查找的底层需要依赖数组,而数组需要的是连续的内存空间,对内存的要求比较苛刻
*/

本文链接: http://www.dtmao.cc/news_show_150011.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?