Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
bug free binary search
/*
*
* 最简单的二分查找. 在一个数组里面找是否存在某个数
* A是数组,在A[p-r]里面找是否存在某个数, 存在返回index,否则返回-1
*
*/
int binSearch(int A[], int p, int r, int v) {
while (p <= r) {
int m = (p+r)/2;
if (A[m] < v) {
p = m + 1; // 注意点: 在不相等的时候一定要+1/-1,这样可以保证考虑的数组范围在每个循环都减小。因此避免死循环。
} else if (A[m] > v) {
r = m - 1;
} else {
// 找到了
return m;
}
}
return -1;
}
// 下面是二分查找的变形。需要用到我的方法
//
// 方法的关键是引入一个辅助变量mark, 来帮助在每个循环都能够缩小范围, 避免死循环
/*
* 变形1: 在数组中找到和v相等的最小的index
* Example:
* search 2 in [1,2,2,3,3,4], return 1
* search 3 in [1,2,2,3,3,4], return 3
*
*
*
*/
int binSearch(int A[], int p, int r, int v) {
int mark = -1; // 首先把mark设为一个不可能的值
// 注意和上面一样,我们考虑的数组范围[p-r], 在每个循环后都减少了,因此避免了死循环
while (p <= r) {
int m = (p+r)/2;
if (A[m] < v) {
p = m + 1;
} else if (A[m] > v) {
r = m - 1;
} else {
// 关键的地方。当A[m] == v时,我们怎么办?
mark = m; // mark保存这个值。因为m可能是我们需要的index.
r = m - 1; // 更新r。因为我们需要返回最小的index.
}
}
return mark;
}
// 思考: 如果需要返回最大的index应该怎么办?
// 变形2:
// 对于一个有序数组[1,2,3,4], 我们从中间折断为[1,2]和[3,4], 然后拼接这个
// 折断后的数组为[3,4,1,2]。
//
// 现在,假如给一个折断后拼接的数组A, 你返回这个数组最小值的index.
// Example:
// [3,4,5,1,2] -> return 3 since A[3] = 1
// 假定数组中所有值都不相同(这个面试的时候要问一下面试官,如果存在相同的值的话
// 这个方法不好使了)
//
// 这题是要我们找小于A[p]的值里面最小的那个。
//
//
int binSearch(int A[], int p, int r) {
int mark = - 1;
int base = A[p]; // 参照值
while (p <= r) {
int m = (p+r) / 2;
if (A[m] < base) {
mark = m; // 找到一个,用mark标记
r = m-1; // 我们试试有没有更小的
} else {
p = m + 1;
}
}
return mark;
}
// 思考:上面这个对于在最左边和最右边切断的case有问题。如何解决?
// Ans: 对于最左边和最右边切断的case, A仍然是一个单调增的有序数组。
//
// 此时,如果使用A[p]为参照值,那么, 最终mark = -1, 因为对于任意x in A[],
// 有: x >= A[p]
//
// 一个想法是改成用A[r]为参照值。
//
// 但是这依然会有问题。那就是当len(A) == 2的时候,而且从中间切断
// 比如, sorted array is [1,2], => A[] is [2,1]. In this time,
// the array is mono dereasing. If we use A[r] as the comparison value, we have
// mark = -1 since for any x in A[], x >= A[r].
//
// Personally, I like to compare it with A[r] since the only corner case
// is when len(A) == 2.
//
// (Note, here we should set the base value before the while loop. Suppose
// we don't use 'base' but A[r] in the while loop for the case {1,2,0,0,1}
// you will find that finally we have A[p] < A[r], i.e., A[p,r] is mono increasing.
// Then the assumption is broken)
//
//
// 思考:如果存在duplicate怎么办?
//
// Ans: We only need to change it a little. The case we need to consider now
// is when A{m] == base.
//
// When A[m] == base, we really don't know how to change value of p and r.
//
// For example,
// A[] = [2,2,3,2,2],
// if m == 1, then A[m] == 2,
// if m == 3, then A[m] also == 2.
//
// As a result, when we encounter the case A[m] == base, we need to do a linear
// search in the range [p,r].
//
// Also, when A[m] == base,
//
// if mark == -1, we know for all numbers x out of range [p,r] in A[], x > A[n],
// so x must not be the position we want.
//
// if mark != -1, we know mark is the left most position outside the range [p,r], so
// that A[mark] < A[n].
//
// So besides numbers in range [p,r], when mark != -1, we also need to consider
// A[mark]
//
int binSearch(int num[], int p, int r) {
int base = num[r];
int mark = -1;
while (p <= r) {
int m = (p+r) / 2;
if (num[m] < base) {
// right
mark = m;
r = m-1;
} else if (num[m] > base) {
// left
p = m+1;
} else {
// A[m] == A[r], so we know we can remove A[r] safely since we still
// have A[m].
// The corner case is when m == r(only one element in the array),
// so we need to update mark.
if (mark == -1 || num[mark] > num[r]) mark = r;
r--;
}
}
return (mark == -1)?r:mark;
}
// 思考: m = (p+r)/2 这断代码存在什么可能的问题?
// Ans: Possible overflow since r may be very large.
// Solution: m = p + (r-p)/2;
@pyq
Copy link

pyq commented Mar 21, 2015

// 思考: 如果需要返回最大的index应该怎么办?
r = m - 1 ==> p = m+1 // means check range [m+1, r] for better potential solution

// 思考:上面这个对于在最左边和最右边切断的case有问题。如何解决?
这种情况是array 就是完全sorted, 在一开始判断 A[0] 和 A[len-1]的大小 如果A[0] < A[len-1](正常sorted array) 直接返回 -1 因为第一个element就是最小的了。 不知道有没有更通用的方法

// 思考:如果存在duplicate怎么办?
如果duplicate 不是首尾字母 貌似不影响 否则就将 r -1?(因为首element还是要用来当base的, 而且末尾element反正相等 不用管,这样也才能判断 切断在哪。)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment