x*****0
发帖数: 452 | 1 基本的binary search有三种变形。
(1) 当无法找到target时，返回insert position。对应leetcode中的 search insert
position
(2) 找到第一次出现target。对应于leetcode中 search for a range和sqrt(x)
(3) 找到最后一次出现的target。对应于leetcode中search for a range
今天下午写了一篇文章，探讨用一种模式写出这三种变形。
http://fihopzz.blogspot.com/2013/07/enter-post-title-here-binar
大家走过路过，不要错过。能提出修改意见，那就更好了。 | x*****0
发帖数: 452 | | s*********d
发帖数: 2406 | | g***j
发帖数: 1275 | 4 我的基本framework是这样的
int xxxx(int x) {
int start = xxx; // the start point to search, for sqrt, it's 1
// generally it's 0, means the first element;
int end = xxx; // the end point to search, for sqrt, it's x
// generally it's n-1, means the last element;
int mid = 0;
while(start <= end ) { // = is needed here
mid = start + (end - start)/2;
if( target == A[mid]) {
return mid; // other stuff for search a range
} else if ( target > A[mid] ) {
start = mid+1;
} else
end = mid-1;
}
return XXXX; // for sqrt, return end, because here end < start
// for insert position, return start
// otherwise, return -1, means not found
}
insert
【在 x*****0 的大作中提到】
: 基本的binary search有三种变形。
: (1) 当无法找到target时，返回insert position。对应leetcode中的 search insert
: position
: (2) 找到第一次出现target。对应于leetcode中 search for a range和sqrt(x)
: (3) 找到最后一次出现的target。对应于leetcode中search for a range
: 今天下午写了一篇文章，探讨用一种模式写出这三种变形。
: http://fihopzz.blogspot.com/2013/07/enter-post-title-here-binar
: 大家走过路过，不要错过。能提出修改意见，那就更好了。
| M*******u
发帖数: 51 | | f*******b
发帖数: 520 | | r********d
发帖数: 7742 | 7 很上心，学习了，赞！
我刚才正好在写search for range，这是我写的search for start和你的不太一样。
int BinarySearchStart(int A[], int lo, int hi, const int &target) {
if (lo > hi) return -1;
while (hi >= lo) {
int mi = lo + (hi-lo)/2;
if (target == A[mi] && (mi-1 < lo || A[mi-1] < target)) {
return mi;
} else if (A[mi] < target) { //have to do this one first
lo = mi+1;
} else {
hi = mi-1;
}
}
return -1;
}
还有就是search rotated，median, 和那个找K in 2 sorted的也都是bsearch。。。或
许也可以总结一下。
insert
【在 x*****0 的大作中提到】
: 基本的binary search有三种变形。
: (1) 当无法找到target时，返回insert position。对应leetcode中的 search insert
: position
: (2) 找到第一次出现target。对应于leetcode中 search for a range和sqrt(x)
: (3) 找到最后一次出现的target。对应于leetcode中search for a range
: 今天下午写了一篇文章，探讨用一种模式写出这三种变形。
: http://fihopzz.blogspot.com/2013/07/enter-post-title-here-binar
: 大家走过路过，不要错过。能提出修改意见，那就更好了。
| r******e
发帖数: 132 | 8 赞啊。学习了。
insert
【在 x*****0 的大作中提到】
: 基本的binary search有三种变形。
: (1) 当无法找到target时，返回insert position。对应leetcode中的 search insert
: position
: (2) 找到第一次出现target。对应于leetcode中 search for a range和sqrt(x)
: (3) 找到最后一次出现的target。对应于leetcode中search for a range
: 今天下午写了一篇文章，探讨用一种模式写出这三种变形。
: http://fihopzz.blogspot.com/2013/07/enter-post-title-here-binar
: 大家走过路过，不要错过。能提出修改意见，那就更好了。
|
|
