Binary Search

Jon Bentley以前说过类似的话:“90%的程序猿无法正确实现二分查找算法

就冲着这句话去写binary search

binary_search 的算法实现部分

/*********************************************************code writer	:	EOFcode file	:	binary_search.ccode date	:	2014.9.18e-mail		:	jasonleaster@gmail.comdescription:	You may have to KNOW that the @array wassequenced from min to max  when you use "binary search".	If this function find the element , return thelocation in the @array, otherwise return -1.********************************************************/#include 
     
      int binary_search(int* array,int size,int element){	if(!array)	{		printf("You passed NULL into function: %s()\n",__FUNCTION__);		return -1;	}	int low = 0;	int mid = 0;	int high= 0;	for(low = 0,high = size-1;low <= high;)	{		mid = (low+high)/2;				if(array[mid] < element)		{			low = mid+1;		}		else if(array[mid] > element)		{			high = mid-1;		}		else		{			/*			** 	found that.			*/			return mid; 		}	}	return -1;}
     

測试用程序

#include 
     
      #include "binary_search.h"int main(){	int number[10] = {0,2,6,8,10,15,18,40,99};	int what_i_want = 18;	int ret = 0;	ret = binary_search(number,sizeof(number)/sizeof(number[0]),what_i_want);	if(ret < 0)	{		printf("Not found!\n");		return 0;	}	printf("location:%d number[%d]:%d\n",ret,ret,number[ret]);	return 0;}
     

update:2015.1.8

加入python版本号的实现

'''Code writer : EOFCode date   : 2015.01.08Code file   : bs.pye-mail      : jasonleaster@gmail.comCode description:       Here is a implementation for how to do binary search in Python.'''def binary_search(array, element):    high = len(array)    mid = -1    for low in range(len(array)) :        mid = (low + high)/2        if array[mid] < element :             low  = mid + 1        elif array[mid] > element :             high = mid - 1        else :             return mid    return -1     def main():    number = [1,2,3,4,5]    print number    print number[binary_search(number,3)]main()

版权声明：本文博客原创文章，博客，未经同意，不得转载。