s********k
发帖数: 6180 | 1 一个数组，比如1,2,3,7,19,8,6,11,34,23,67.
find local min，就是比它左右都小，比如这个里面的6比8,11小，23比34,67小，都是
local min。找到任意一个local min就可以
找出比O(n)更好的办法。二分法找显然是方向，但是这个题的细节考虑可能比较多。 | n******t
发帖数: 4406 | 2 Looks to me you need to go through all elements at least once to solve it, n
ot sure how you want to do it better than O(n).
【在 s********k 的大作中提到】
: 一个数组，比如1,2,3,7,19,8,6,11,34,23,67.
: find local min，就是比它左右都小，比如这个里面的6比8,11小，23比34,67小，都是
: local min。找到任意一个local min就可以
: 找出比O(n)更好的办法。二分法找显然是方向，但是这个题的细节考虑可能比较多。
| l*********8
发帖数: 4642 | 3 是要求找到所有的local min 吗？如果是，那么最少O(n）时间。
【在 s********k 的大作中提到】
: 一个数组，比如1,2,3,7,19,8,6,11,34,23,67.
: find local min，就是比它左右都小，比如这个里面的6比8,11小，23比34,67小，都是
: local min。找到任意一个local min就可以
: 找出比O(n)更好的办法。二分法找显然是方向，但是这个题的细节考虑可能比较多。
| l*********8
发帖数: 4642 | 4 就算只找一个local min, 平均和最差也是O(n)时间。
【在 l*********8 的大作中提到】
: 是要求找到所有的local min 吗？如果是，那么最少O(n）时间。
| s********k
发帖数: 6180 | 5 只找到任意一个就可以了。
【在 l*********8 的大作中提到】
: 是要求找到所有的local min 吗？如果是，那么最少O(n）时间。
| s********k
发帖数: 6180 | 6 Binary search可以做，但是cases貌似也比较多。
【在 l*********8 的大作中提到】
: 就算只找一个local min, 平均和最差也是O(n)时间。
| l*********8
发帖数: 4642 | 7 又不是sorted array，怎么binary search?
【在 s********k 的大作中提到】
: Binary search可以做，但是cases貌似也比较多。
| s********k
发帖数: 6180 | 8 比如a[mid]
there must be a local min between begin and mid. recursive do.
但是这个可能性情况稍微有点复杂
【在 l*********8 的大作中提到】
: 又不是sorted array，怎么binary search?
| l***i
发帖数: 1309 | 9 check a[mid-1], a[mid] and a[mid+1], then recurse on left OR right. O(log n)
个人感觉这个题挺没劲的，见过的一下就出来了，没见过的除非很牛才能想到把。
高级板，2D matrix， find local minimum，
a[i][j] is local min if a[i][j] <= a[i-1][j], a[i+1][j], a[i][j-1], a[i][j+1
] | L*****9
发帖数: 18 | 10 I can think of a binary-search-style of approach with worst case O(N) and
average O(log(N)).
Start with comparing A[0], A[N/2], and A[N]. If these three numbers are of a
b>c, or ac style, then we have to repeat the similar comparison
for *both* the left part [0..N/2] and the right part [N/2..N].
If however, the three numbers are of (good) pattern a>b
to follow
*one* of the following three cases in each of the remaining steps:
i) if the left part has the good pattern, repeat for the left and skip the
right part;
ii) if the right part has the good pattern, repeat for the right and skip
the left;
iii) if none of the above, then based on the existing (good) pattern from
the current round, we *must* have middle_of_left>current_middle
right, therefore we continue the remaining steps for the region [middle_of_
left, middle_of_right].
In all the above three cases, the property of "good pattern" is preserved,
and therefore we can continue the strategy of "only work on half of the
region from the previous round" until the size of the region becomes 3 and
we've found a local minimum, and therefore the cost finding a local minimum
in any region [start, end] with the "good pattern" is log(sizeof([start, end
])).
Now let's see how long it takes to reach a region with "good pattern". This
is important because before reaching such a region, we have to work on both
parts, as mentioned at the beginning, and therefore the cost for this part
is O(2^k), where k is the rounds we need before reach a "good pattern".
The entire process includes the inefficient steps before find a region with
"good pattern" and the efficient steps afterwards, and therefore the total
cost would be O(2^k) + log(N/2^k).
In the worst case, we have to do k=log(N) rounds to find such a (good)
region, i.e., we need O(N) time to find a local minimum. For example, the
following sequence
{1, 2, 3, 4, 5, 6, ...., N-3, N-2, 0, N}
On average, however, my guess is the cost would still be O(log(N)), because
k remains to be a small number in "most cases" for a randomly permuted
sequence of numbers.
By "most cases", I mean, the probability of requiring k rounds to reach/find
a good region seems to be about 4/k!.
【在 s********k 的大作中提到】
: 一个数组，比如1,2,3,7,19,8,6,11,34,23,67.
: find local min，就是比它左右都小，比如这个里面的6比8,11小，23比34,67小，都是
: local min。找到任意一个local min就可以
: 找出比O(n)更好的办法。二分法找显然是方向，但是这个题的细节考虑可能比较多。
| | | J***2
发帖数: 135 | 11
这个不是sorted array, 怎么能binary search 呢？ 请指教
【在 s********k 的大作中提到】
: Binary search可以做，但是cases貌似也比较多。
| l*******b
发帖数: 2586 | 12 这个题。。。讲average就是胡扯了吧。。。如果数列完全随机，顺序查找貌似平均是
常数时间。。。
假设后一个数比前一个数大的概率大约1/2，那基本上找到第2，第3项就已经有local
min了
a
need
【在 L*****9 的大作中提到】
: I can think of a binary-search-style of approach with worst case O(N) and
: average O(log(N)).
: Start with comparing A[0], A[N/2], and A[N]. If these three numbers are of a
: b>c, or ac style, then we have to repeat the similar comparison
: for *both* the left part [0..N/2] and the right part [N/2..N].
: If however, the three numbers are of (good) pattern a>b: to follow
: *one* of the following three cases in each of the remaining steps:
: i) if the left part has the good pattern, repeat for the left and skip the
: right part;
| l*******b
发帖数: 2586 | 13 如果讲最坏情况，数列递增或者递减，怎么找都是O(n)
local
【在 l*******b 的大作中提到】
: 这个题。。。讲average就是胡扯了吧。。。如果数列完全随机，顺序查找貌似平均是
: 常数时间。。。
: 假设后一个数比前一个数大的概率大约1/2，那基本上找到第2，第3项就已经有local
: min了
:
: a
: need
| d*********g
发帖数: 154 | 14
a
need
很有意思的方法，学习了。只是最后两段的分析不是很明白，特别是最后一段的4/k!
【在 L*****9 的大作中提到】
: I can think of a binary-search-style of approach with worst case O(N) and
: average O(log(N)).
: Start with comparing A[0], A[N/2], and A[N]. If these three numbers are of a
: b>c, or ac style, then we have to repeat the similar comparison
: for *both* the left part [0..N/2] and the right part [N/2..N].
: If however, the three numbers are of (good) pattern a>b: to follow
: *one* of the following three cases in each of the remaining steps:
: i) if the left part has the good pattern, repeat for the left and skip the
: right part;
| L*****9
发帖数: 18 | 15 哦,你说的有道理.这么说这题出得就不对? 还是有些条件原题没有写清?
local
【在 l*******b 的大作中提到】
: 这个题。。。讲average就是胡扯了吧。。。如果数列完全随机，顺序查找貌似平均是
: 常数时间。。。
: 假设后一个数比前一个数大的概率大约1/2，那基本上找到第2，第3项就已经有local
: min了
:
: a
: need
| l*******b
发帖数: 2586 | 16 我觉得是不太对。。。可能理解不到位吧，大牛指教
【在 L*****9 的大作中提到】
: 哦,你说的有道理.这么说这题出得就不对? 还是有些条件原题没有写清?
:
: local
| s********k
发帖数: 6180 | 17 我觉得说的有道理，其实binary search未见得在实际中比直接过一遍好，当然理论分
析貌似更好，但是我相信如果实际系统中有这个要求，恐怕还是简单办法好。
【在 L*****9 的大作中提到】
: 哦,你说的有道理.这么说这题出得就不对? 还是有些条件原题没有写清?
:
: local
| c**s
发帖数: 159 | 18 找一个的话 有O(logn)算法
可以这样想：
假设没有相等的数，首先对任意子序列local minimal一定存在，因为最小值就是一
个满足条件的数
假设第一个数>第二个数 （否则第一个数就是）
同理考虑倒数第二个 倒数第二个 < 最后一个 （否则最后一个数就是）
然后我们可以2分，对中间位置x 用p[x]表示x位置的数 有4种情况：
(1) p[x - 1] < p[x] < p[x + 1] 则可以取前一半继续找 因为它和前一半的情况
一样
（2）p[x - 1] > p[x] > p[x + 1] 则可以取后一半继续找
（3）p[x - 1] < p[x] p[x] > p[x + 1] 则取前一半后一半都可以
(4) p[x - 1] > p[x] p[x] < p[x + 1] 则p[x]就是 | r*****n
发帖数: 35 | 19
【在 c**s 的大作中提到】
: 找一个的话 有O(logn)算法
: 可以这样想：
: 假设没有相等的数，首先对任意子序列local minimal一定存在，因为最小值就是一
: 个满足条件的数
: 假设第一个数>第二个数 （否则第一个数就是）
: 同理考虑倒数第二个 倒数第二个 < 最后一个 （否则最后一个数就是）
: 然后我们可以2分，对中间位置x 用p[x]表示x位置的数 有4种情况：
: (1) p[x - 1] < p[x] < p[x + 1] 则可以取前一半继续找 因为它和前一半的情况
: 一样
: （2）p[x - 1] > p[x] > p[x + 1] 则可以取后一半继续找
| y*****a
发帖数: 221 | 20 不明白了 考虑这个问题
Given an array of n mumbers, in which one element is 0 and all others are 1
, find the index of this 0 element.
What is the worst case complexity? O(n)? | | | s********k
发帖数: 6180 | 21 但是我发现这个方法确实不一定比直接过一遍好，当时我也是老是想的多，因为两者在
worst case下都是O(n)，然后究竟哪个事实中快难说。
【在 c**s 的大作中提到】
: 找一个的话 有O(logn)算法
: 可以这样想：
: 假设没有相等的数，首先对任意子序列local minimal一定存在，因为最小值就是一
: 个满足条件的数
: 假设第一个数>第二个数 （否则第一个数就是）
: 同理考虑倒数第二个 倒数第二个 < 最后一个 （否则最后一个数就是）
: 然后我们可以2分，对中间位置x 用p[x]表示x位置的数 有4种情况：
: (1) p[x - 1] < p[x] < p[x + 1] 则可以取前一半继续找 因为它和前一半的情况
: 一样
: （2）p[x - 1] > p[x] > p[x + 1] 则可以取后一半继续找
| l*******b
发帖数: 2586 | 22 嗯，这个方法是对的吧。关键在于，端点也可以是local min。。。老想着local min只
能在数组中间
【在 s********k 的大作中提到】
: 但是我发现这个方法确实不一定比直接过一遍好，当时我也是老是想的多，因为两者在
: worst case下都是O(n)，然后究竟哪个事实中快难说。
| s********k
发帖数: 6180 | 23 端点不能使local min。
【在 l*******b 的大作中提到】
: 嗯，这个方法是对的吧。关键在于，端点也可以是local min。。。老想着local min只
: 能在数组中间
| l*******b
发帖数: 2586 | 24 看起来出题的人是这样认为的呀，或者就是要你考虑到这一层然后问他端点可不可以是
local min
【在 s********k 的大作中提到】
: 端点不能使local min。
| y*****a
发帖数: 221 | 25 根据找到这个， 问题有两点要加强
1. 数是不等的
2. 端点可以为local minimal
http://coder40.blogspot.com/2010/02/local-minimum-of-array.html
Problem: Given an array a of N distinct integers, design an O(log N)
algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+
1].
My answer: If a[0] < a[1] or a[N - 2] > a[N - 1] then a[0] or a[N - 1] is
the local minimum, respectively. Pick a[mid] where mid = N / 2. If it's not
the answer, we have three cases:
1) If a[mid - 1] < a[mid] < a[mid + 1], lower half will contain the
local minimum.
2) If a[mid - 1] > a[mid] > a[mid + 1], upper half will contain the
local minimum.
3) If a[mid - 1] < a[mid] > a[mid + 1], either half will contain the
local minimum.
Search on the new interval recursively.
【在 s********k 的大作中提到】
: 一个数组，比如1,2,3,7,19,8,6,11,34,23,67.
: find local min，就是比它左右都小，比如这个里面的6比8,11小，23比34,67小，都是
: local min。找到任意一个local min就可以
: 找出比O(n)更好的办法。二分法找显然是方向，但是这个题的细节考虑可能比较多。
| w****x
发帖数: 2483 | 26 /*
Suppose we are given an array A[1 .. n] with the special property that A[1]
≥A[2] and
A[n − 1] ≤A[n]. We say that an element A[x] is a local minimum if it
is less than or equal
to both its neighbors, or more formally, if A[x − 1] ≥A[x] and A[x]
≤A[x + 1]. For example,
there are five local minima in the following array:
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
We can obviously find a local minimum in O(n) time by scanning through
the array. Describe
and analyze an algorithm that finds a local minimum in O(log n) time
*/
int findLocalMin(int a[], int n)
{
assert(a && n > 2);
int nBeg = 0;
int nEnd = n-1;
while (nBeg <= nEnd)
{
int nMid = nBeg + (nEnd - nBeg)/2;
if (nMid > 0 && nMid < n-1 && a[nMid-1] >= a[nMid] && a[nMid+1] >= a
[nMid])
return nMid;
if ((nMid == n-1) || (a[nMid] <= a[nMid+1])) //less equal than not
less
nEnd = nMid - 1;
else nBeg = nMid + 1;
}
return -1;
} | f*******g
发帖数: 11 | 27 按照这样二分查找，可不可能最终找不到存在的local min？
i+
not
【在 y*****a 的大作中提到】
: 根据找到这个， 问题有两点要加强
: 1. 数是不等的
: 2. 端点可以为local minimal
: http://coder40.blogspot.com/2010/02/local-minimum-of-array.html
: Problem: Given an array a of N distinct integers, design an O(log N)
: algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+
: 1].
: My answer: If a[0] < a[1] or a[N - 2] > a[N - 1] then a[0] or a[N - 1] is
: the local minimum, respectively. Pick a[mid] where mid = N / 2. If it's not
: the answer, we have three cases:
| j*****y
发帖数: 1071 | 28 int localMin(int A[], int n)
{
if(n == 1)
{
return A[0];
}
if(A[0] < A[1])
{
return A[0];
}
if(A[n - 1] < A[n - 2])
{
return A[n - 1];
}
int left = 0, right = n - 1;
int mid = 0;
while(left + 1 < right)
{
mid = (left + right) / 2;
if(A[mid - 1] > A[mid] && A[mid] < A[mid + 1])
{
break;
}
else if(A[mid - 1] < A[mid])
{
right = mid;
}
else
{
left = mid;
}
}
return A[mid];
}
【在 f*******g 的大作中提到】
: 按照这样二分查找，可不可能最终找不到存在的local min？
:
: i+
: not
| i******t
发帖数: 52 | 29 随机的数组 是O（N）， 但是如果两头满足A[0] ≥ A[1] and A[n − 2] ≤ A[n
-1]， 可以
http://www.careercup.com/question?id=8223978 | l*******s
发帖数: 1258 | 30 说下我的想法：
把这个题目转化成解析几何：在某个坐标系里，给定一段函数曲线，已知这个曲线处处
可导且有拐点。
要求：找出导数为0的点，找到一个就行。
思路：暂时没想到。（哥没学过高数。。。） | | | l*******s
发帖数: 1258 | 31 这个答案不对
反例：0,1,2,3,4,5,6,50,49,51,2
a[mid]=5, a[mid-1] < a[mid] < a[mid+1]
按照答案所说，结果应该在左侧，但是明显正确答案应该在右侧。
同样的反例，能举出好多。
i+
not
【在 y*****a 的大作中提到】
: 根据找到这个， 问题有两点要加强
: 1. 数是不等的
: 2. 端点可以为local minimal
: http://coder40.blogspot.com/2010/02/local-minimum-of-array.html
: Problem: Given an array a of N distinct integers, design an O(log N)
: algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+
: 1].
: My answer: If a[0] < a[1] or a[N - 2] > a[N - 1] then a[0] or a[N - 1] is
: the local minimum, respectively. Pick a[mid] where mid = N / 2. If it's not
: the answer, we have three cases:
| j********g
发帖数: 80 | 32 左侧难道不是正确的么？？？？ 这题是找出一个就行，不管哪一个
【在 l*******s 的大作中提到】
: 这个答案不对
: 反例：0,1,2,3,4,5,6,50,49,51,2
: a[mid]=5, a[mid-1] < a[mid] < a[mid+1]
: 按照答案所说，结果应该在左侧，但是明显正确答案应该在右侧。
: 同样的反例，能举出好多。
:
: i+
: not
| l*******s
发帖数: 1258 | 33 不对。
按照他那个说法，就跑到左边找答案去了。而0,1,2,3,4,5,6,50,49,51,2这个例子中，
正确答案在右边。 | p*****2
发帖数: 21240 | | j********g
发帖数: 80 | 35 0 就是个答案阿。 我想关键问题是端点算不算的问题吧，算的话O(lgn)，不算的话就
得O(n)了
【在 l*******s 的大作中提到】
: 不对。
: 按照他那个说法，就跑到左边找答案去了。而0,1,2,3,4,5,6,50,49,51,2这个例子中，
: 正确答案在右边。
| y***m
发帖数: 7027 | 36 这样可否:
二分递归思路, 假设都是正整数, 数组 a[n]
f 函数三比一, g 函数二分递归
bool f(a1,a2,a3)
{
return a2
}
int g(a[1..n])
{
if n 偶:
if n >= 4
{
m=n/2
if f(a[m-1],a[m],a[m+1])
return a[m];
else if f(a[m],a[m+1],a[m+2])
return a[m=1];
else
{
int rst = g(a[1...m/2]);
if(rst>0)
return rst;
else
return g(a[m/2...n]);
}
}
else
return -1;
//////////////////////////////// 同理
else 奇:
if n >= 3
{
m=四舍五入(n/2)
if f(a[m-1],a[m],a[m+1])
return a[m]
if(m>2)
{
int rst = g(a[m-2],a[m-1],a[m]);
if rst > -1
return rst;
else
return g(a[m],a[m+1],a[m+2]);
}
return -1;
}
else
return -1;
}
【在 s********k 的大作中提到】
: 一个数组，比如1,2,3,7,19,8,6,11,34,23,67.
: find local min，就是比它左右都小，比如这个里面的6比8,11小，23比34,67小，都是
: local min。找到任意一个local min就可以
: 找出比O(n)更好的办法。二分法找显然是方向，但是这个题的细节考虑可能比较多。
| d**********n
发帖数: 132 | | l*******s
发帖数: 1258 | 38 确实 端点算的话 就对了
【在 j********g 的大作中提到】
: 0 就是个答案阿。 我想关键问题是端点算不算的问题吧，算的话O(lgn)，不算的话就
: 得O(n)了
| y****n
发帖数: 743 | 39 这道题，我认为理论上O(n)已经是最佳答案了。
所谓二分法，原数组必定要有些规律，才可以二分，否则分了也白分。
举个极端的例子：
{1,1,1,1, ... ,1,0,1,1, ... ,1,1}
这种情况，找到中间那个0，只可能O(n)。
针对这道题，所有的“优化”方法，不过是调整不同的读数顺序。
但是，无论你怎样调整，你不能保证那个LocalMin会更早被发现。
这句话对于可能有多个LocalMin的情况一样适用。
所以，如果数组是无规律的，算法应该是O(n)，几乎没有优化空间。
而在实际工作中，我们有可能根据LocalMin经常实现的位置或频率稍加调整。 | p*****2
发帖数: 21240 | 40
膜拜一山大牛。好久不见指点江山了。
【在 y****n 的大作中提到】
: 这道题，我认为理论上O(n)已经是最佳答案了。
: 所谓二分法，原数组必定要有些规律，才可以二分，否则分了也白分。
: 举个极端的例子：
: {1,1,1,1, ... ,1,0,1,1, ... ,1,1}
: 这种情况，找到中间那个0，只可能O(n)。
: 针对这道题，所有的“优化”方法，不过是调整不同的读数顺序。
: 但是，无论你怎样调整，你不能保证那个LocalMin会更早被发现。
: 这句话对于可能有多个LocalMin的情况一样适用。
: 所以，如果数组是无规律的，算法应该是O(n)，几乎没有优化空间。
: 而在实际工作中，我们有可能根据LocalMin经常实现的位置或频率稍加调整。
| | | y****n
发帖数: 743 | 41 过奖了。
时不时瞎忙一阵，时不时回来做做题，保持着一颗随时面试的心。
【在 p*****2 的大作中提到】
:
: 膜拜一山大牛。好久不见指点江山了。
| y****n
发帖数: 743 | 42 这道题还有一个比较麻烦的地方。
如LZ所说，是G家面试题。但是G家面试题怎会如此简单？但重循环比大小？
有没有可能面试官自己也误认为此题有“优化”空间，从而把最好的答案判了死刑。 | r**d
发帖数: 90 | 43 原体
Suppose we are given an array A[1 .. n] with the special property that A[1]
≥ A[2] and
A[n − 1] ≤ A[n]. We say that an element A[x] is a local minimum if
it is less than or equal
to both its neighbors, or more formally, if A[x − 1] ≥ A[x] and A[x]
≤ A[x + 1]. For example
it's possible to be logn
【在 y****n 的大作中提到】
: 这道题还有一个比较麻烦的地方。
: 如LZ所说，是G家面试题。但是G家面试题怎会如此简单？但重循环比大小？
: 有没有可能面试官自己也误认为此题有“优化”空间，从而把最好的答案判了死刑。
| y****n
发帖数: 743 | 44 按照新贴的原题，的确可以logn，二分法，根据中点方向每次折半。 | p*****2
发帖数: 21240 | 45
你理解两边可以算local min吗？
【在 y****n 的大作中提到】
: 按照新贴的原题，的确可以logn，二分法，根据中点方向每次折半。
| y****n
发帖数: 743 | 46 按照新贴的原题，两端不可能出现local min。
A[1] ≥ A[2] and A[n − 1] ≤ A[n]
【在 p*****2 的大作中提到】
:
: 你理解两边可以算local min吗？
| p*****2
发帖数: 21240 | 47
奥。看错了。这样就应该可以了。
【在 y****n 的大作中提到】
: 按照新贴的原题，两端不可能出现local min。
: A[1] ≥ A[2] and A[n − 1] ≤ A[n]
| p*****2
发帖数: 21240 | 48
不过worst case还是O(n)把
【在 y****n 的大作中提到】
: 按照新贴的原题，的确可以logn，二分法，根据中点方向每次折半。
| l*****a
发帖数: 14598 | 49 不知道一大牛这些年面了几家
【在 y****n 的大作中提到】
: 过奖了。
: 时不时瞎忙一阵，时不时回来做做题，保持着一颗随时面试的心。
| y****n
发帖数: 743 | 50 二分法：我使用C#，数组范围A[0..n-1]，假设输入数组符合条件。
public static int FindLocalMin(int[] arr)
{
int start = 0;
int end = arr.Length - 1;
while (end - start > 2)
{
int mid = (end + start) / 2;
if (arr[mid] < arr[mid + 1])
end = mid + 1;
else
start = mid;
}
return arr[start + 1];
}
]
x]
【在 r**d 的大作中提到】
: 原体
: Suppose we are given an array A[1 .. n] with the special property that A[1]
: ≥ A[2] and
: A[n − 1] ≤ A[n]. We say that an element A[x] is a local minimum if
: it is less than or equal
: to both its neighbors, or more formally, if A[x − 1] ≥ A[x] and A[x]
: ≤ A[x + 1]. For example
: it's possible to be logn
| | | y****n
发帖数: 743 | 51 我一共也没面试过几次，Onsite实战经验不多。
【在 l*****a 的大作中提到】
: 不知道一大牛这些年面了几家
| p*****2
发帖数: 21240 | 52
不错呀。很牛。
【在 y****n 的大作中提到】
: 二分法：我使用C#，数组范围A[0..n-1]，假设输入数组符合条件。
: public static int FindLocalMin(int[] arr)
: {
: int start = 0;
: int end = arr.Length - 1;
: while (end - start > 2)
: {
: int mid = (end + start) / 2;
: if (arr[mid] < arr[mid + 1])
: end = mid + 1;
| l*****a
发帖数: 14598 | 53 据说，二分法能写对的人不多
【在 p*****2 的大作中提到】
:
: 不错呀。很牛。
| p*****2
发帖数: 21240 | 54
嗯。我本来想总结一下呢。还没时间呢。想看看到底有多少trick在里边。
【在 l*****a 的大作中提到】
: 据说，二分法能写对的人不多
| y***m
发帖数: 7027 | 55 测试了么 { 3, 5, 9, 11, 2,6 }
【在 y****n 的大作中提到】
: 二分法：我使用C#，数组范围A[0..n-1]，假设输入数组符合条件。
: public static int FindLocalMin(int[] arr)
: {
: int start = 0;
: int end = arr.Length - 1;
: while (end - start > 2)
: {
: int mid = (end + start) / 2;
: if (arr[mid] < arr[mid + 1])
: end = mid + 1;
| y****n
发帖数: 743 | 56 你的用例不符合原题条件： A[1] ≥ A[2]
【在 y***m 的大作中提到】
: 测试了么 { 3, 5, 9, 11, 2,6 }
| w***g
发帖数: 5958 | 57 赞犀利。这个反例找的非常好。面试的时候要是能给出这个反例我觉得就应该给过。
1
【在 y*****a 的大作中提到】
: 不明白了 考虑这个问题
: Given an array of n mumbers, in which one element is 0 and all others are 1
: , find the index of this 0 element.
: What is the worst case complexity? O(n)?
|
|
