二分法在搜索插入位置中不同写法的分析

探讨究竟是left < right还是left <= right

前言

最近复习C++,看到一篇很好的介绍二分法的文章,这里分享一下:
just click me
文中提到了二分法的两种写法,我在此想分享一下我的分析~

二分法简介

当我们想在一个有序数组中查找某一个值target时,我们可以直接将target与数组中间的值比较大小,根据比较的结果,我们可以直接过滤掉一半的数据,二分法就是不断重复这一过程,试图找到一个与target相等的值的算法。

分析例题

LeetCode题库

编号35:搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素

示例 1:
输入: [1,3,5,6], 5
输出: 2

示例 2:
输入: [1,3,5,6], 2
输出: 1

示例 3:
输入: [1,3,5,6], 7
输出: 4

示例 4:
输入: [1,3,5,6], 0
输出: 0

注意是无重复元素,此时使用二分法可保证结果唯一

两种二分法区别分析

我们先思考一下使用二分法的结果,除了正常查找到合适的位置外,就是left与right的值最终重合到最小值或者最大值上,注意这是两种二分法循环条件不同的重要原因。

再提出我的结论,根据right的取值决定二分法种类

nums=[1,3,5,6]为例,有四个元素,对应下表为0,1,2,3。初始时left取值为0,而right可以取值为nums.size()-1值为3,对应第四个元素下标。或者取值为nums.size(),值为4,因为有四个元素;对应以下两种情况:

1:当取值nums.size()-1时,nums[right]为最后一个元素,此时查找范围是[left,right],对应我们常用的二分法,当target < nums[middle]时,说明从middle开始右面的值全部大于target,于是我们可以令right = middle - 1(因为middle大于target,所以到middle左面一个元素为止),同理,当target > nums[middle]时,我们可以将范围缩小到[middle + 1, right],当最终rightleft重合于最大或最小值时,由于是闭区间,仍在有效范围,所以循环条件为(left <= right)

2:当取值nums.size()时,由于nums[right]无意义(越界),则查找的范围是[left,right),此时当target < nums[middle]时,说明从middle开始右面的值全部大于target,于是我们可以另right = middle(右面为开区间,所以到middle即可),而当target > nums[middle]时,因为左侧为闭区间,我们要将范围缩小到[middle + 1, right],当最终right与left重合于最大或最小值时,由于存在开区间,超出有效范围,所以循环条件为(left < right)也可以直观的理解为本情况的right比情况1的right大1,所以当left等于right时,实际left已经大于right,因此不用探讨等于的情况。

对于最终循环外的返回值,可以像原文一样使用right + 1或者right来区分不同方式,也可以全部返回left,两种情况下left的值都是最终插入位置。

结语

我的文笔不太好,可能写的有点乱,以上内容也仅是我个人分析,如有谬误请一定指出,谢谢~

上一篇:二分法实现开平方(JAVA实现)


下一篇:HTML入门笔记必看