二分查找

发表于

描述
请实现无重复数字的升序数组的二分查找

给定一个 元素升序的、无重复数字的整型数组nums和一个目标值target，写一个函数搜索nums中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回-1

数据范围： 0≤len(nums)≤2*105 ,数组中任意值满足 |val|≤109
要求： 时间复杂度O(logn)，空间复杂度O(1)

示例1

1
2
3
输入:  [-1,0,3,4,6,10,13,14],13
返回:  6
说明:  13 出现在nums中并且下标为 6

示例2

1
2
3
输入:  [],3
返回:  -1
说明:  nums为空，返回-1

示例3

1
2
3
输入:  [-1,0,3,4,6,10,13,14],2
返回:  -1
说明:  2 不存在nums中因此返回 -1

题解

分支算法

  • 从数组首尾开始，每次取中点值
  • 如果中间值等于目标即找到了，可返回下标，如果中点值大于目标，说明中点以后的都大于目标，因此目标在中点左半区间，如果中点值小于目标，则相反
  • 根据比较进入对应的区间，直到区间左右端相遇，意味着没有找到
二分查找.gif 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package main


/**
 *
 *
 * @param nums int整型一维数组
 * @param target int整型
 * @return int整型
 */
func search( nums []int ,  target int ) int {
    // write code here
    left, rigth := 0, len(nums) - 1
    for left <= rigth {
        middle := left + (rigth-left)/2
        if nums[middle] == target {
            return middle
        } else if nums[middle] > target {
            rigth = middle - 1
        } else {
            left = middle + 1
        }
    }

    return -1
}