二分查找

# -*- coding: utf-8 -*-
# binary_search

def binary_search(list_1, item):

    low = 0
    high = len(list_1)-1

    while low <= high:
        '''使用 // 整除运算符可以不用int进行类型转换'''
        #每次都检查中间的元素
        mid = (low + high)/2
        guess = list_1[int(mid)]

        if guess == item:
            return int(mid)#返回所在位置的索引
        if guess < item:   #猜的数字小了，修改low
            low = mid+1
        if guess > item:   #猜的数字大了，修改high
            high = mid-1
    return None

def main():

    list_2 = [1,2,3,4,5,6,7,8,9]

    print(binary_search(list_2, 8))
    print(binary_search(list_2, 10))

main()

#include<iostream>
#include<typeinfo>
using namespace std;

int binary_search(int a[9],int n,int x)//n为元素个数
{
    int mid;
    int high,low=0;
	int guess;

    high = n-1;//数组下标从0开始

	while(low <= high)
    {
        mid = (high+low)/2;
        guess = a[mid];
        if(guess == x)
            return mid;
        if(guess > x)
            high = mid-1;
		if(guess < x)
		    low = mid+1;
    }
    return -1;
}

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

	cout<<sizeof(a)/sizeof(int)<<endl;
	cout<<typeid(sizeof(a)/sizeof(int)).name()<<endl;
    temp = binary_search(a,sizeof(a)/sizeof(int),5);
	cout<<temp<<endl;

	return 0;
}