I**A
发帖数: 2345 | 1 Given a sorted list of N integers that has been rotated an unknown number of
positions, e.g., 15 36 1 7 12 13 14。 design an lg(n) algorithm to
determine if a given integer is in the list
你们谁写过code，可否share share? 我比较着比较着就乱了。。 | j**l
发帖数: 2911 | 2 如果没有重复元素
假定当前搜索区间开始的下标是s, 中点的下标是m, 结束的下标是e,
要查找的数是x，可以证明A[s] <= A[m]和A[m] <= A[e]至少有一个成立
if (s > e)
查找失败返回;
m = (s + e) / 2;
if (x == A[m] || x == A[s] || x == A[e])
查找成功返回;
if (A[s] <= A[m])
{
if (x > A[s] && x < A[m]
在区间[s+1, m-1]继续找
else
在区间[m+1, e-1]继续找
}
else if (A[m] <= A[e])
{
if (x > A[m] && x < A[e]
在区间[m+1, e-1]继续找
else
在区间[s+1, m-1]继续找
}
else
{
// This is not possible if the original array is circular sorted
} | I**A
发帖数: 2345 | 3 多谢多谢！let me see see...
【在 j**l 的大作中提到】
: 如果没有重复元素
: 假定当前搜索区间开始的下标是s, 中点的下标是m, 结束的下标是e,
: 要查找的数是x，可以证明A[s] <= A[m]和A[m] <= A[e]至少有一个成立
: if (s > e)
: 查找失败返回;
: m = (s + e) / 2;
: if (x == A[m] || x == A[s] || x == A[e])
: 查找成功返回;
: if (A[s] <= A[m])
: {
| l******e
发帖数: 12192 | 4 这么多分支，还不如先找pivot
在二分
【在 j**l 的大作中提到】
: 如果没有重复元素
: 假定当前搜索区间开始的下标是s, 中点的下标是m, 结束的下标是e,
: 要查找的数是x，可以证明A[s] <= A[m]和A[m] <= A[e]至少有一个成立
: if (s > e)
: 查找失败返回;
: m = (s + e) / 2;
: if (x == A[m] || x == A[s] || x == A[e])
: 查找成功返回;
: if (A[s] <= A[m])
: {
| j**l
发帖数: 2911 | 5 递归版
int binSearch(int s[], int start, int end, int num)
{
if (start > end)
return -1;
int mid = (start + end) / 2;
if (num == s[start] || num == s[end] || num == s[mid])
{
if (num == s[end])
mid = end;
else if (num == s[start])
mid = start;
return mid;
}
if (s[start] <= s[mid])
{
if( num > s[start] && num < s[mid])
return binSearch(s, start + 1, mid - 1, num);
else
re | t****a
发帖数: 1212 | 6 agree with larabee.
1. binary search pivot
2. binary search x. | j**l
发帖数: 2911 | 7 迭代版，改编自Careercup 150题的解答, 分支更多
int binSearch(int s[], int start, int end, int num)
{
while (start <= end)
{
int mid = (start + end) / 2;
if (num == s[mid])
return mid;
if (s[start] <= s[mid])
{
if (num > s[mid])
start = mid + 1;
else if (num >= s[start])
end = mid - 1;
else
start = mid + 1;
}
else /* s[mid] <= s[end] */
{
| j**l
发帖数: 2911 | 8 二分法找pivot (reset point)的下标, 假定没有重复元素
int findResetPoint(int s[], int start, int end)
{
if (s == NULL || start < 0 || end < 0 || start > end)
return -1;
// At least three elements in the range
while (end - start > 1)
{
// sorted case, no rotation
if (s[start] < s[end])
return start;
int mid = (start + end) / 2;
if (s[mid] < s[mid - 1])
return mid;
if (s[start] < s[mid])
start = mid + 1;
els | I**A
发帖数: 2345 | 9 多谢大家！
的确是先找pivot的时候， 思路要简单明了
【在 j**l 的大作中提到】
: 二分法找pivot (reset point)的下标, 假定没有重复元素
: int findResetPoint(int s[], int start, int end)
: {
: if (s == NULL || start < 0 || end < 0 || start > end)
: return -1;
: // At least three elements in the range
: while (end - start > 1)
: {
: // sorted case, no rotation
: if (s[start] < s[end])
| j**l
发帖数: 2911 | 10 补充一下，如果不限定while中至少有三个元素，
则一个元素的情形: start == mid == end
而两个元素的情形: start == mid, start + 1 == end
也就是start, mid和end发生了粘连，这会导致一些麻烦的边界情形，
比如start == end == mid == 0, mid - 1就越界了
原来只需要判断s[start] < s[mid], 要改为判断s[start] <= s[mid]了
【在 j**l 的大作中提到】
: 二分法找pivot (reset point)的下标, 假定没有重复元素
: int findResetPoint(int s[], int start, int end)
: {
: if (s == NULL || start < 0 || end < 0 || start > end)
: return -1;
: // At least three elements in the range
: while (end - start > 1)
: {
: // sorted case, no rotation
: if (s[start] < s[end])
| y*********e
发帖数: 518 | 11 贴一贴我的Java代码，希望有帮助！
/*
* Given a sorted array, which is rightwards rotated X steps.
* Find X.
*/
public static int findRotate(int[] array) {
return findRotate(array, 0, array.length - 1);
}
/*
* Approach:
*
* Find the first element pair x, y such that x > y.
* Then the index of x is the answer.
*
* 1. Take the median value. If it is greater than its previous
* element, then the index of the median is what we look for.
| j**l
发帖数: 2911 | 12 有几个值得商榷的地方
0. 描述中应该是x > y的时候，返回y的下标而不是x的下标
1. 我们是在数组的子段，也就是闭区间[low, high]找，最后对应not rotated at all
， 应该返回low,也就是第一个元素,而不是返回0
2. 如果while中发现当前的子段一开始就是严格有序没有rotated, 则可以提前返回，
不需要总共迭代大约logN次后才返回
3. corner case不能和0比，应该和low比，考虑下面的test case
array = [7 4 3], low = 1, high = 2
也就是子段[4 3]中找pivot, 应该是返回3的下标
程序计算出mid == 1 > 0, 但忽视mid和low相等，从而越过low得到7, 发现7 > 4， 返
回了4的下标
4. 当low == high的时候，mid == high,
如下的语句
if (midVal < array[high])
就漏过了相等的情形而使得low被设置为high + 1, 根据第1条我们最后返回low，也就不对了，offset by 1。
public stat
【在 y*********e 的大作中提到】
: 贴一贴我的Java代码，希望有帮助！
: /*
: * Given a sorted array, which is rightwards rotated X steps.
: * Find X.
: */
: public static int findRotate(int[] array) {
: return findRotate(array, 0, array.length - 1);
: }
: /*
: * Approach:
| j**l
发帖数: 2911 | 13 对很多基本二分查找的变体题目，
如果我们让while处理三个元素(含)以上的情形，边界情况的困难就被消除了
然后while外头处理两个元素或一个元素的情形是很容易的
while (high - low > 1)
{
// 处理至少三个元素，无需边界处理
}
// 处理至多两个元素
当然，我发过相关的帖子，如果你遇到固执的面试官，不理解你为何那样处理，非要
很隐晦地暗示你必须采用如下的传统处理(最适用基本二分查找，因为几乎没有边界处理)
while (low <= high)
{
// 一堆容易出错的边界处理
}
那也只能顺其所好，考虑周全，好好把while里头各种边界情况写好吧。否则面完后被拒不说，还被背地里扣上不能很好follow面试官的suggestion的帽子。 |
|
