二分（折半）查找

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

在最坏的情况下用O(log n)完成搜索任务。

---

java实现：

public class BinarySearch {

    public int binarySearch(int[] arr,int target)
    {
        if (arr.length==0||arr==null)
            return -1;

        int min = 0;
        int max = arr.length-1;
        int mid = ((max-min)>>1)+min;

        while (min<=max)
        {
            if (arr[mid]<target)
                min = mid + 1;
            else if (arr[mid]>target)
                max = mid - 1;
            else
                return mid;
            mid = ((max-min)>>1)+min;
        }
        return -1;
    }
}