C 语言折半查找的例子

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

有一个数组 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本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

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

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

《重来:更为简单有效的商业思维》 贾森•弗里德(Jason Fried) (作者), 大卫•汉森(David Heinemeier Hansson) (作者), Mike Rohde (插图作者), 李瑜偲 (译者)

这本书呈现的是一种更好、更简单的经商成功之道。读完这本书,你就会明白为什么计划实际上百害而无一益,为什么你不需要外界投资人,为什么将竞争视而不见反倒会发展得更好。事实是你所需要的比你想象的少得多。你不必成为工作狂,你不必大量招兵买马,你不必把时间浪费在案头工作和会议上,你甚至不必拥有一间办公室。所有这些都仅仅是借口!

更多计算机宝库...