给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜寻 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输出: nums = [-1,0,3,5,9,12], target = 9
输入: 4
解释: 9 呈现在 nums 中并且下标为 4

示例 2:

输出: nums = [-1,0,3,5,9,12], target = 2
输入: -1
解释: 2 不存在 nums 中因而返回 -1

提醒:

你能够假如 nums 中的所有元素是不反复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

原题链接:https://leetcode.cn/problems/...

思路:
升序无反复元素数组,能够思考下应用二分查找法,二分查找常见公式:

func binySearch(target int) (res int) {    left := 0    right := ……    for 条件 {        mid := left + (right-left)/2        if nums[mid] == target {            return mid        } else if nums[mid] > target {            right = ……        } else if nums[mid] < target {            left = ……        }    }    return -1}

留神:golang 没有while 循环

有了这个常见公式,然而不晓得细节怎么写?right 初始化的时候是多少,循环条件 right >= left 还是 right > left。 right 的值是等于mid-1, 还是等于mid。

次要是因为对区间的定义没有想分明,区间的定义就是不变量,既然这样定义了这个规定,就贯彻到底,这样在二分查找的过程中方得始终。

常见二分查找有两个思路,左闭右闭区间即[left, right], 或者左闭右开区间即[left, right)

题解一:定义 target 是在一个在左闭右闭的区间里查找,也就是[left, right],right地位可达,所以最大值为数组长度-1

func search(nums []int, target int) int {    // 左闭,数组下标从0开始    left := 0    // 右闭,值为数组长度-1,地位可达,并且无效    right := len(nums) - 1    // 因为right=len(nums)-1    // 元素地位是可能是len(nums)-1的    // 也就是left=right    // target能够在[0, len(nums) - 1]区间查找    for right >= left {        //避免溢出        mid := left + (right-left)/2        //找到指标元素地位,返回后果        if nums[mid] == target {            return mid        } else if nums[mid] > target {            //target 在左区间            //持续放弃左闭右闭            //也就是[left, mid-1]            //mid 地位不合乎,有可能前一个元素合乎            right = mid - 1        } else if nums[mid] < target {            //target 在左区间,持续放弃左闭右闭            //left 地位不合乎,有可能下一个元素合乎            left = mid + 1        }    }    return -1   }

题解二:定义 target 是在一个在左闭右开的区间里查找,也就是[left, right),right地位不可达

func search(nums []int, target int) int {    //左闭,下标从0开始    left := 0    //右开,值为数组长度, 地位不可达,不可拜访    right := len(nums)    // 数组下标从0开始    // left最大值为数组长度-1    // 也就是left永远小于right    // target只在[0, len(nums))区间查找    // 否则无意义    for right > left {        //避免溢出        mid := left + (right-left)/2        //找到指标元素地位,返回后果        if nums[mid] == target {            return mid        } else if nums[mid] > target {            //target 在左区间,            //mid 地位不合乎,有可能前一个元素合乎。            //持续放弃为左开右闭,所以写为[left, mid)            right = mid        } else if nums[mid] < target {            //target 在左区间            //left 地位不合乎,有可能下一个元素合乎            //持续放弃为左开右闭            left = mid + 1        }    }    return -1}

总结

二分法为什么一看就会,一写就废?次要就是在定义完区间后,在循环体内,没有保持查找区间的定义来做边界解决。始终如一,不忘初心,许可我不要做一个花心的渣男好吗?