二分查找正确位置的直观证明与数学证明

https://leetcode.com/problems/search-insert-position/

直观证明

low == mid == high：如果 target > nums[mid]，则正确答案为 mid + 1，low = mid + 1 正确，high 不变错误；如果 target < nums[mid]，则正确答案为 mid，low 不变正确，high = mid - 1 错误。

low == mid == high - 1：如果 target > nums[mid]，则 low = mid + 1，此轮不是最后一轮，low == mid == high，进入第一种情况；如果 target < nums[mid]，则正确答案为 mid，low 不变正确，high = mid - 1 错误。

数学证明

1638861506379.jpg
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 二分查找【python总结】
    将原本是线性时间提升到了对数时间log(N)范围，大大缩短了搜索时间 前提，必须在有序数据中进行查找。 1. 最基...
    惊不意外阅读 9,029评论 0赞 3
  • 算法 | 下次面试遇到二分查找，别再写错了
    点赞关注，不再迷路，你的支持对我意义重大！Hi，我是丑丑。本文「数据结构 & 算法」| 导读 —— 登高博见[ht...
    彭旭锐阅读 5,817评论 1赞 6
  • 二分查找
    非递归版本 递归版本 对二分查找分析 在N个有序数组中，进行二分查找最多需要(log2N + 1)次比较(无论是否...
    wayyyy阅读 1,196评论 0赞 0
  • 算法3：二分查找
    二分查找是一种在有序列表中查找元素的高效方法，时间复杂度（logN），二分查找思路和时间都比较简单，但是实际问题中...
    HYIndex阅读 2,885评论 0赞 0
  • 二分查找
    关于查找有许多种算法，二分查找是一种十分高效的算法，其时间复杂度为O（logn）。 如果在相册中查找一张照片，我们...
    Tander阅读 1,085评论 0赞 0