C 语言折半查找的例子

折半查找是很常见的一个算法
服务器君一共花费了314.635 ms进行了8次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素。数组中有个元素 x,如何知道 x 位于该数组的第几位呢?

解决这个问题的一个普遍方法是折半查找。下面是程序:

#include <stdio.h>
int binsearch(int x, int v[], int n);
main()
{
    int i, result, n;
	int wait;
    
    int x = 17;	// 需要查找的数值
	int v[19]; // 定义一个数组
	// 给数组赋值
	for(i = 0; i < 20; ++i)
    	v[i] = i;
	/**
	for(i = 0; i < 20; ++i)
		printf("%d \n", v[i]);
	*/
	n = 20;
	result = binsearch(x, v, n);
	printf("%d", result);
	scanf("%d", &wait);
}
int binsearch(int x, int v[], int n)
{
	int low, high, mid;
	low = 0;
	high = n - 1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if(x < v[mid])
			high = mid - 1;
		else if (x > v[mid])
			low = mid + 1;
		else
			return mid;
		// 看看循环执行了多少次
		printf("mid = %d, low = %d, high = %d \n", mid, low, high);
	}
	return -1;
}

思路很简单:首先将输入值 x 与数组 v 的中间元素比较,如果 x 小于中间的元素,则将 high 值设为 中间元素-1,同理,若 x 大于中间元素,则将中间元素 + 1作为 low,再在low 与 high之间进行查找。

本文地址:http://www.nowamagic.net/librarys/veda/detail/523,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/523

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《Python学习手册(第4版)》 鲁特兹(Mark Lutz) (作者), 李军 (译者), 刘红伟 (译者), 等 (译者)

《Python学习手册(第4版)》学习Python的主要内建对象类型:数字、列表和字典。使用Python语句创建和处理对象,并且学习Python的通用语法模型。使用函数构造和重用代码,函数是Python的基本过程工具。学习Python模块:封装语句、函数以及其他工具,以便构建较大的组件。学习Python的面向对象编程工具,用于组织程序代码。学习异常处理模型,以及用于编写较大程序的开发工具。了解高级Python工具,如装饰器、描述器、元类和Unicode处理等。

更多计算机宝库...