二分搜索

二分搜索简单说就是在一个有序的数组中利用二分法的方法搜索我们需要的元素O(logn)。
直接看代码！

 

import java.util.Arrays;

/**
* 用java语言实现二分搜素
* @author Administrator
*
*/
public class BianarySerch {


public static void main(String[] args) {
//定义一个数组,数组必须是有序的，二分查找只能针对有序表;
int[] a={1,2,4,22,33,34,45,48,102,302};
int keyType=22;
//数组排序
Arrays.sort(a);
int ans=BinaSerch(a,keyType);
if(ans==-1){
System.out.println("表中没有该元素");
}else{
System.out.println("已经找到元素,在表中的位置是:"+ans);
}
}

/**
* 二分查找法;
* @param a--数据表;
* @param keyType
*/
public static int BinaSerch(int [] a, int keyType){
int mid;//中间变量;
//定义位置标记;
int start=0,end=a.length-1,site;
while(start<=end){
site=(start+end)/2;
mid=a[site];//取中间值;
if(mid==keyType){
return site;
}else if(mid<keyType){
start=site+1;
}else{
end=site-1;
}
}
return -1;//表示没有找到该元素;
}

}

 

下面用Python实现二分搜索：

'''
Created on 2012-8-2

@author: luliang
'''
#!/usr/bin/env python

aList=[2,6,3,6,2,8]

def binarySerch(num,left,right):
    mid=(left+right)/2
    if right>=left:
        if num==aList[mid]:
            print 'find it the position is:',mid
        else:
            if num<aList[mid]:
                return binarySerch(num, left, mid-1)
            if num>aList[mid]:
                return binarySerch(num, mid, right)

binarySerch(3,0,len(aList)-1)