C语言编程中实现二分查找的简单入门实例

架设有一个数组 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;

}

1、二分查找法

二分查找法有一个很重要的前提条件：即待查找的序列必须是已经排好序的。

假设元素序列是按升序排列，将序列中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将序列分成前、后两个子序列，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子序列，否则进一步查找后一子序列。重复以上过程，直到找到满足条件的记录，查找成功，返回元素在序列中的索引，或直到子序列不存在为止，此时查找失败，返回-1。