二分查找

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
*/
func search( nums []int ,  target int ) int {
    if len(nums) == 0 {
        return -1
    }
    low := 0
    high := len(nums) - 1

    for low <= high {
        mid := low + ((high - low) >> 1)
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

要注意的点：

• 非递归实现，循环退出条件注意是 low <= high
• mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是将 mid 的计算方式写成 low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。
• low 和 high 的更新 low=mid+1，high=mid-1