11.1 二分查找基础

若在长度为n的数组中查找数字, 全部遍历需要时间O(n).

若数组是有序的, 那么每次只用在一半的元素中查找即可, 时间O(logn)

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    
    for left <= right {
        mid := (left+right) / 2
        
        if target == nums[mid] {
            return mid
        }

        if target > nums[mid] {
            left = mid + 1
        }
        
        if target < nums[mid] {
            right = mid - 1
        }
    }

    return -1
}

Reference

1. 剑指Offer（专项突破版）