二分查找法

代码

public class binarySearch{
    public static int Search(int [] array, int target) {
        int start = 0;
        int end = array.length - 1;
        int mid;
        while (start <= end) {
            mid = start + (end - start)/2;
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int [] array = new int[1000];
        for (int i=0; i<1000; i++) {
            array[i] = i;
        }
        System.out.println(Search(array, 173));
    }
}

解释

为何 mid = start + (end -start)/2 为何不能写成 mid = (start + end)/2 ?

解释：start，end均为整型数据，int型数据的最大值为2147483647。

若此时

n=Integer.MAX_VALUE;
start=Integer.MAX_VALUE-1
end=Integer.MAX_VALUE

那么此时，(start+end)必超过整型数据的返回，自然会出现问题.