谈谈二分搜索

今天读编程珠玑发现这句有意思的话：“提供充足的时间，竟然仅有10%的专业程序员能将这个小程序（指二分搜索）编写正确。” 于是随便写了写：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


//
//  二分搜索.c
//  
//  说明：本质是二分法求根。
//
//  Created by 欧 长坤 on 13-11-05.
//  Copyright (c) 2013年 欧 长坤. All rights reserved.
//

#include <stdio.h>

int binary_search(int array[], int left, int right, int key)
{
	int middle;
	while(left <= right)
	{
		middle = (left + right)/2;
		if (array[middle] == key)
			return middle;// position
		else if(array[middle] > key)
			right = middle - 1;
		else
			left = middle + 1;
	}
	return -1;// not find
}

int main()
{
	int array[10] = {1,2,3,4,5,6,7,8,9,10};

	int ret = binary_search(array, 0, 10, 1);
	if(ret != -1)
		printf("position is %d\n", ret);
	else
		printf("can not find\n");
}