leetcode Ch1-search 2014
class Solution {
public:
int searchInsert(int A[], int n, int target) {
int left=,right=n-;
while(left<=right)
{
int mid=left+(right-left)/;
if(A[mid]==target) return mid;
if(A[mid]<target)
left=mid+;
else right=mid-;
}
return left;
}
};
当循环结束时，如果没有找到目标元素，那么left一定停在恰好比目标大的元素的index上，right一定停在恰好比目标小的index上.
特殊点的例子：当在{1,2,3,4,5}里执行二分查找找0时，此时的left=0, right=-1.(left和right也是挺拼的，为了比target大/小，不惜越界。)
这个规律非常有用，合理利用left和right在未找到target的情况下退出while循环时的特性，能解决很多问题，尤其体现在实现upperBound和lowerBound函数时。如果要利用left或right，需要保证target不在当前区间内，这样才能让while循环以未找到target的状态退出。为了实现这一点，我们需要在即使发现target==A[mid]的情况下仍然假装没看见，继续缩小搜索范围。
因此如果要在二分搜索的基础上计算bound的话，其实就是怎么处理那几个值为target的元素的问题。也就是是否把这部分值恰好为target的元素纳入下一轮搜索范围。(二分搜索本质上就是不断缩小搜索范围)。
以upperBound为例。upperBound函数是找[left,right]内第一个大于target的元素下标------所以值为target的元素肯定要排除在搜索范围之外。这样当A[mid]==target时我们仍将其排除在搜索范围外，即让low=mid+1。一直到搜索范围里已经没有值为target的元素了，此时根据二分查找的性质，当区间里没有找到target时，while循环退出后low指向刚好大于target的位置，high指向刚好小于target的位置。所以此时我们返回low即为刚好大于target的位置，即——第一个大于target的位置。
lowerBound同理。lowerBound是寻找[left,right]内第一个值不小于target的元素下标。“不小于”target的不好求，但刚好小于target的那个元素位置比较好求，因为这就是right的返回值。所以我们按照上述思路，在遇到A[mid]==target的情况下仍假装看不见，继续缩小搜索范围，直到当前范围里没有了target，最终循环退出时right就指向值刚好小于target的元素位置。而（right+1）即为不小于target的元素下标。
lowerBound和upperBound的实现代码在下一题代码中。
What if there are duplicates?
class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
int left=,right=n-;
vector<int> res(,-);//[-1,-1]是默认值
while(left<=right)
{
int mid=left+(right-left)/;
if(A[mid]<target)
left=mid+;
else if(A[mid]>target)
right=mid-;
else
{
res[]=lowerBound(A,left,mid,target);
res[]=upperBound(A,mid,right,target)-;//别忘了减1
return res;
}
}
return res;//这一句别忘了。当查找失败时返回[-1,-1].
}
private:
int upperBound(int A[], int left, int right, int target)
{
int low = left, high = right;
while (low <= high)
{
int mid = low + (high - low) / ;
if (A[mid] <= target)
low = mid + ;
else
high = mid - ;
}
return low;
}
int lowerBound(int A[], int left, int right, int target)
{
int low = left, high = right;
while (low <= high)
{
int mid = low + (high - low) / ;
if (A[mid] >= target)
high = mid - ;
else
low = mid + ;
}
return high + ;
}
};
lowerBound和upperBound与binarySearch之间的关系上一题里已经分析过了。
注意几个小细节，已在注释中标明。细节决定成败，bug-free需要谨小慎微。
3. Search in Rotated Sorted Array
class Solution {
public:
int search(int A[], int n, int target) {
int left=,right=n-;
while(left<=right)
{
int mid=left+(right-left)/;
if(A[mid]==target) return mid;
if(A[mid]<A[right])//说明右半段是有序的
{
if(target>A[mid]&&target<=A[right])
left=mid+;
else
right=mid-;
}
else
{
if(target>=A[left]&&target<A[mid])
right=mid-;
else
left=mid+;
}
}
return -;
}
};
最关键的把握这个规律："总有一半是有序的，而且和另一半无区间重叠"。code ganker的总结很好。
4. Search in Rotated Sorted Array II
class Solution {
public:
bool search(int A[], int n, int target) {
for(int i=;i<n;i++)
if(A[i]==target) return true;
return false;
}
};
由于允许有duplicates，会导致没有办法像I中那样根据A[mid]和A[left]、A[right]的比较来确定是哪一半有序，应该在哪一半查找。
导致最坏时间复杂度变为O(n)。因此用最简单的遍历来实现就可以。
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
if(matrix.size()==||matrix[].size()==) return false;
int m=matrix.size(); int n=matrix[].size();
int left=,right=m*n-;
while(left<=right)
{
int mid=left+(right-left)/;
int midX=mid/n; int midY=mid%n;//注意：这里是n，不是m！
if(matrix[midX][midY]==target) return true;
if(matrix[midX][midY]<target)
left=mid+;
else
right=mid-;
}
return false;
}
};
6. sqrt(x)
class Solution {
public:
int sqrt(int x) {
if(x<) return x;
int left=,right=x/+;
while(left<=right)
{
int mid=left+(right-left)/;
if(mid<=x/mid&&(mid+)>x/(mid+))//防止溢出
return mid;
if(mid>x/(mid))
right=mid-;
else
left=mid+;
}
return -;
}
};
比较蹊跷的是if(mid>x/mid)和下面的else不能换位置。尚不知为何。
最新文章
- 20155315庄艺霖--对做中学的理解及对c语言和Java的看法
- FFMpeg video duration
- Webstorm 下的Angular2.0开发之路
- Access restriction: The type TaskTopicResolver is not accessible due to restrict
- Laravel如何优雅的使用Swoole
- PostgreSQL的 initdb 源代码分析之十一
- RTC之初始化
- BZOJ 1037 [ZJOI2008]生日聚会Party
- 所闻所获6：meditashayne项目总结
- OSI参考模型初识
- linux下python2升级python3，python2和python3并存
- 【aardio】如何对listview中某一列，某一行的特定值进行修改？
- 将python、pip 加入环境变量
- redis-cli 连接远程服务器
- SQLite3学习笔记----创建数据库的两种方式
- Weblogic Maven
- es第十篇：Elasticsearch for Apache Hadoop
- git base 简单命令行
- easyui首页模板
- 在Oracle Linux上安装dtrace