Algorithms►算法

Dichotomy

二分法作为比较基础的算法，虽然工作中不常使用，但是作为编程基础，还是很有必要整理下的，下面是二分法的一个版本的代码，记录在blog，以备后面查看温习。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
 
int BSearch(int d[], int target, int low, int high)
{
	int m;
	while (low <= high)
	{
		m = (low + high) / 2;
		if (target < d[m])
			high = m - 1;
		else if (target>d[m])
			low = m + 1;
		else
			return m;
	}
	return -1;
}
 
int  main(int argc, char *argv[])
{
	int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int c = BSearch(a, 5, 0, 10);
	printf("index:%d\n", c);
}

Compile and Run

1
2
3
gcc main.c -o main
./main
index:4