简明现代魔法 -> C/C++ -> C 程序设计:折半查找

C 程序设计:折半查找

2010-07-15

有一个数组 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之间进行查找。

随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们