注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
在看这个讲binary search的帖子, 不是很明白他的invariant relation是怎么确定的
为什么第一题是 A[start] < target <= A[end].
第二题是 A[start] <= target < A[end]. ?
求解释!!
还有一个问题是 能不能直接把framework改成
int binarySearchFramework(int A[], int n, int target) {
int start = start index of array - 1;
int end = length of the A;
while (end - start > 1) {
int mid = (end - start) / 2 + start;
if(A[mid]==target) return mid;
if (A[mid] < target) {
end = mid;
} else {
start = mid;
}
}
//not found
...
}
这样会引入新的问题吗?
我还是很想知道他的那两个invariant relation是怎么确定的!!!
谢谢!
|