题目

给定一个升序整数数组，写一个函数搜索 nums 中数字 target。如果 target 存在，返回它的下标，否则返回 -1。

注意，这个数组的大小是未知的。你只可以通过 ArrayReader 接口访问这个数组，ArrayReader.get(k) 返回数组中第 k 个元素（下标从 0 开始）。

  • 可以认为数组中所有的整数都小于 10000。如果你访问数组越界，ArrayReader.get 会返回 2147483647。

样例 1：

  1. 输入: array = [-1,0,3,5,9,12], target = 9
  2. 输出: 4
  3. 解释: 9 存在在 nums 中，下标为 4

样例 2：

  1. 输入: array = [-1,0,3,5,9,12], target = 2
  2. 输出: -1
  3. 解释: 2 不在数组中所以返回 -1

注释 ：

  • 可以认为数组中所有元素的值互不相同。
  • 数组元素的值域是 [-9999, 9999]。

方案一（迭代）

  1. func search(reader ArrayReader, target int) int {
  2.     var i = 0
  3.     for {
  4.         var item = reader.get(i)
  5.         if item == target {
  6.             return i
  7.         } else if item == 2147483647 {
  8.             return -1
  9.         }
  10.         i += 1
  11.     }
  12. }
  • 时间复杂度 搜索长度未知的有序数组 - 图1

方案二（二分查找）

  1. func search(reader ArrayReader, target int) int {
  2.     // 特殊值处理
  3.     if reader.get(0) == target {return 0}
  4.     // 找到合适的 right 节点，时间复杂度 O(logn)
  5.     var right = 1 // 2^right, 不能从0开始，否则左移操作就失效了
  6.     for {
  7.         var item = reader.get(right)
  8.         if item == target {
  9.             return right
  10.         } else if item > target {
  11.             break
  12.         } else {
  13.             right = right << 1 // 平方            
  14.         }
  15.     }
  16.     // 二分查找
  17.     var left = 0
  18.     for left <= right {
  19.         var mid = (left + right) / 2
  20.         var item = reader.get(mid)
  21.         if item == target {
  22.             return mid
  23.         } else if item > target {
  24.             right = mid - 1
  25.         } else {
  26.             left = mid + 1
  27.         }
  28.     }
  30.     return -1
  31. }
  • 时间复杂度 搜索长度未知的有序数组 - 图2

方案三（优化方案二）

  1. func search(reader ArrayReader, target int) int {
  2.     // 特殊值处理
  3.     if reader.get(0) == target {return 0}
  4.     // 找到合适的 right 节点，时间复杂度 O(logn)
  5.     var left, right = 1, 1 // 2^end
  6.     for {
  7.         var item = reader.get(right)
  8.         if item == target {
  9.             return right
  10.         } else if item > target {
  11.             break
  12.         } else {
  13.             left = right
  14.             right = right << 1 // 平方            
  15.         }
  16.     }
  17.     // 进行二分查找
  18.     for left <= right {
  19.         var mid = (left + right) / 2
  20.         var item = reader.get(mid)
  21.         if item == target {
  22.             return mid
  23.         } else if item > target {
  24.             right = mid - 1
  25.         } else {
  26.             left = mid + 1
  27.         }
  28.     }
  30.     return -1
  31. }
  • 寻找 right 节点时，就固定 left 节点位置

原文

https://leetcode-cn.com/explore/learn/card/binary-search/212/template-analysis/849/