有一个数组 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,欢迎访问原出处。
大家都在看