Hello everyone , I meet you again , I'm the king of the whole stack , I've prepared for you today Idea Registration code .

Binary Search

Jon Bentley I have said similar words before :“90% The program ape of cannot correctly implement the binary search algorithm

Just write this sentence binary search

binary_search Algorithm implementation part of

/*********************************************************
code writer	:	EOF
code file	:	binary_search.c
code date	:	2014.9.18
e-mail		:	[email protected]

description:
	You may have to KNOW that the @array was
sequenced from min to max  when you use "binary search".

	If this function find the element , return the
location in the @array, otherwise return -1.

********************************************************/
#include <stdio.h>

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

Copy

Test procedure

#include <stdio.h>
#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;
}

Copy

update:2015.1.8

Join in python Implementation of version number

'''
Code writer : EOF
Code date   : 2015.01.08
Code file   : bs.py
e-mail      : [email protected]

Code 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()

Copy

Copyright notice ： This article is an original blog article , Blog , Without consent , Shall not be reproduced .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/117659.html Link to the original text ：https://javaforall.cn