Leetcode之Search for a Range 问题
问题描述:
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(logn).
If the target is not found in the array, return [-1, -1]
.
示例:
Given [5, 7, 7, 8, 8, 10]
and target value 8,
return [3, 4]
.
问题来源:Search for a Range (详细地址:https://leetcode.com/problems/search-for-a-range/description/)
思路分析:相信大部分看到这道题有个很明显的思路就是二分查找,但是这道题虽然也是二分查找,但是在此基础之上又改进了一下,需要好好分析一下。
解法一:我们可以先二分查找找到这个元素,接着这个数肯定在这个数的周围,但是时间复杂度不是o(logn),而是o(n).有同学说不是o(n),而是O(n/2),O(n/3)等等,这取决于有几个有几个相同的数了,而我觉得这些都是线性时间的时间复杂度,因此概括为O(n);
解法二:同样也是二分查找,我们可以先找到左边界,接着找到右边界。先谈谈左索引(最左边的等于target的那个数),具体的操作就是我们首先找到一个等于该数的索引,但是我们不停下来,我们继续寻找。继续往左寻找,寻找到左索引为止,下面列一列本来二分查找的三种情况:
1) if(nums[mid] == target) return mid;
2) if(nums[mid] < target) low = mid + 1;
3) if(nums[mid] > target) high = mid - 1;
但是放到这道题的话,我们需要找到左边界的索引,第一种情况我们改进一下,其实这个mid要么就是左索引了,要么左索引就在该元素的左边,翻译成代码就是:high = mid;接下来我们把1)和3)合并起来,得到的就是high = mid,即:
1‘) if(nums[mid] < target) low = mid + 1
2’) if(nums[mid] >= target) high = mid;
有人会问,好端端的合并啥啊?其实合并起来就是便于操作,不用再分的那么仔细了,这样最后low指针返回的就是左索引了。下面举个例子,就拿上面的[5, 7, 7, 8, 8, 10],target = 8,循环的标准是low < high(和以前的二分查找好像有点不一样,以前都是low <= high)好了:
第一步:low = 0, high = 5, mid = 2,指向的是7<8,接着该往右走了;
第二步:low = 3, high = 5, mid = 4, 指向的是8=8,可以看出左边界一定在左边或者就是这个数本身,low < high接着往左走;
第三步:low = 3, high = 4,mid = 3,指向的是8 = 8,可以看出来我们往左边走了,但此时还是low < high,所以还是要往左走;
第四步:low = 3,high = 3,mid = 3,指向的是8 = 8,可以看出我们已经到左边界了,而正好此时low = high,跳出循环,知道为啥这是low < high执行循环而不是low <= high,如果是的话这里就是死循环了。
这样,我们就找到左边界了,直接返回low的索引就是左边界了!
同理,我们需要找到右边界,这里二分的情况就分为:
1’) if(nums[mid] <= target) low = mid;(右索引一定位于该数的右边或者就是这个数本身)
2‘) if(nums[mid] > target) high = mid - 1;
在这还有个小细节,不然就陷入死循环,low如果仍然是low = (low + high) / 2,这就会陷入死循环,不信你自己试试,这是什么原因呢?中间值不一直都是这么求的吗?这是因为我们以前求的mid值都是偏向左边的,你发现没?因为int取的就是左整数,因此我们在这求右边界的时候,我们要让它偏向右边,如何操作呢?在这两种操作都行:
操作一:low = low + (high - low + 1) / 2;
操作二:low = low + (high - low) / 2 + 1.
这样我们所有的细节都介绍完了,你可能看的也点晕了,那我们直接上代码吧,看代码可能好一些。
代码:
寻找左边界:
寻找右边界: