g**4
发帖数: 863 | 1 做binary search相关题的时候，经常会遇到mid要不要加1或减1
另外比如Search in Rotated Sorted Array这题，要比较A[start] <= A[mid],这里为
什么是小于等于，而不是小于
有没大牛分析过此类情况？ |
r*******e
发帖数: 971 | 2 有，我。
假定你的三个指针是low mid high
简单三句话
1 终止条件决定了 high 如何操作，一般来说,while(low
（low<=high） high＝mid－1；
2.要根据实际情况，确定是否要排除mid 然后确定终止条件
3.low 永远是 low ＝ mid＋1； |
y*******r
发帖数: 141 | 3 一个办法是 while(min + 1 < max), 循环外分别判断A[min], A[max], 适用大多场合
。 |
l*****a
发帖数: 14598 | 4 结果正确
但是对很多时候是冗余的。
【在 y*******r 的大作中提到】
: 一个办法是 while(min + 1 < max), 循环外分别判断A[min], A[max], 适用大多场合
: 。
|
l*****a
发帖数: 14598 | 5 得看情况，low不见得总是mid+1
比方说找一个数在sorted array中的最大index
while
【在 r*******e 的大作中提到】
: 有，我。
: 假定你的三个指针是low mid high
: 简单三句话
: 1 终止条件决定了 high 如何操作，一般来说,while(low: （low<=high） high＝mid－1；
: 2.要根据实际情况，确定是否要排除mid 然后确定终止条件
: 3.low 永远是 low ＝ mid＋1；
|
r*******e
发帖数: 971 | 6 这种情况也可以low ＝ mid ＋1
while(low<=high){
mid = low+(high-low)/2;
if (A[mid]>target)
high=mid-1;
else
low = mid+1;
}
return high;//这句是关键
如果return low 那就是像你说的那样了。
【在 l*****a 的大作中提到】
: 得看情况，low不见得总是mid+1
: 比方说找一个数在sorted array中的最大index
:
: while
|
l*****a
发帖数: 14598 | 7 please try to find 2 in[0,1] with your code
【在 r*******e 的大作中提到】
: 这种情况也可以low ＝ mid ＋1
: while(low<=high){
: mid = low+(high-low)/2;
: if (A[mid]>target)
: high=mid-1;
: else
: low = mid+1;
: }
: return high;//这句是关键
: 如果return low 那就是像你说的那样了。
|
r*******e
发帖数: 971 | 8 只要做个前检验就好了，这种情况就不用搜索了，O（1） 复杂度，多么和谐。你说是
吧。
【在 l*****a 的大作中提到】
: please try to find 2 in[0,1] with your code
|
r*******e
发帖数: 971 | 9 然后这个 return 难道不是1 么？？
如果找不到就返回最接近的那个呗，看实际要求了。
【在 l*****a 的大作中提到】
: please try to find 2 in[0,1] with your code
|
l*****a
发帖数: 14598 | 10 the how about find 1 in [0,2]?
still O(1)?
【在 r*******e 的大作中提到】
: 只要做个前检验就好了，这种情况就不用搜索了，O（1） 复杂度，多么和谐。你说是
: 吧。
|
|
|
l*****a
发帖数: 14598 | 11 return -1吧
没出现怎么能返回1
【在 r*******e 的大作中提到】
: 然后这个 return 难道不是1 么？？
: 如果找不到就返回最接近的那个呗，看实际要求了。
|
r*******e
发帖数: 971 | 12 哈，搜完了看看 A[high]==target 是否成立，不成立返回-1呗，就多一行。
【在 l*****a 的大作中提到】
: the how about find 1 in [0,2]?
: still O(1)?
|
L********e
发帖数: 25 | 13 nice!
while
【在 r*******e 的大作中提到】
: 有，我。
: 假定你的三个指针是low mid high
: 简单三句话
: 1 终止条件决定了 high 如何操作，一般来说,while(low: （low<=high） high＝mid－1；
: 2.要根据实际情况，确定是否要排除mid 然后确定终止条件
: 3.low 永远是 low ＝ mid＋1；
|
k****s
发帖数: 16 | 14 写个 返回最后一次数字出现的位置 试试
while
【在 r*******e 的大作中提到】
: 有，我。
: 假定你的三个指针是low mid high
: 简单三句话
: 1 终止条件决定了 high 如何操作，一般来说,while(low: （low<=high） high＝mid－1；
: 2.要根据实际情况，确定是否要排除mid 然后确定终止条件
: 3.low 永远是 low ＝ mid＋1；
|
r*******e
发帖数: 971 | 15 Leetcode上面的search range吧，我就是用我自己说的解法做的
【在 k****s 的大作中提到】
: 写个 返回最后一次数字出现的位置 试试
:
: while
|
h****u
发帖数: 71 | |
