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;
}

思路很簡單：首先將輸入值 x 與數組 v 的中間元素比較，如果 x 小於中間的元素，則將 high 值設為 中間元素-1，同理，若 x 大於中間元素，則將中間元素 + 1作為 low，再在low 與 high之間進行查找。