tang7526
10/15/2016 - 7:37 PM

binarySearch模版

binarySearch模版

public int binarySearch(int[] nums, int target)
{
    if (nums == null || nums.length == 0)
    {
        return -1;
    }
    int start = 0;
    int end = nums.length - 1;
    while (start + 1 < end)
    {
        int mid = start + (end - start) / 2;
        if (target < nums[mid])
        {
            end = mid;
        }
        else if (target > nums[mid])
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }
    if (nums[start] == target)
    {
        return start;
    }
    if (nums[end] == target)
    {
        return end;
    }
    return -1;
}

Keypoints:
1. 對輸入做異常處理:陣列為空或者陣列長度為0。
2. int mid = start + (end - start) / 2 這種表示方法可以防止兩個整型值相加時溢出。
3. Recursion or While-Loop:使用迭代而不是遞迴進行二分查找,因為工程中遞迴寫法存在潛在溢出的可能
4. while循環終止條件:while終止條件應為start + 1 < end而不是start <= end,start == end時可能出現死循環,即循環終止條件是相鄰或相交元素時退出。配合while終止條件start + 1 < end(相鄰即退出)的賦值語句mid永遠沒有+1或者-1,這樣不會死循環。
5. 迭代終止時target應為start或者end中的一個。循環終止條件有兩個,具體應看是找第一個還是最後一個而定。