64,636
社区成员
发帖
与我相关
我的任务
分享算法求助（面试题），如何利用二分法查找数组中的值
有两个int数组，一个数组的每个元素都存在于另一个数组中，要求在O(sqrt(n))情况下，找出一个数组中每个元素在另一个数组中的位置。
面试官提示用二分查找，把整个数组合在一起做二分查找，小弟无能，没有做出来。不知道哪位高手能不能解答一下？
面试官提示用二分查找，把整个数组合在一起做二分查找，小弟无能，没有做出来。不知道哪位高手能不能解答一下？
...全文
请发表友善的回复…
发表回复
huangjunjie_1985 2009-08-14
- 打赏
- 举报
算了，我个人觉得28楼说的有道理，考官也确实提到过通过对B的比对快速找出在A数组中的位置。我没怎么理解。
xinshou2595 2009-08-13
- 打赏
- 举报
汗~~~~没看懂题目
poor_student 2009-08-13
- 打赏
- 举报
expecting
nihuajie05 2009-08-13
- 打赏
- 举报
我想问LZ，你的O（SPRT(N)）是否包括前续的处理时间，是整个程序时间呢还是仅仅是查找时间
如果是整个程序工程的时间复杂度，我觉得很难达到，连B数组的一次遍历都不能做，就能完成所有的查找，属我愚笨，不胜惶恐。
如果仅仅是查找过程的话，你的这个复杂度，是不是有点宽裕了。好多东西都可以用呀。。。
PS：（我还真是第一次看见SPRT（N）的时间复杂度。。。LG（N）倒是勉强见过几次）
如果是整个程序工程的时间复杂度，我觉得很难达到，连B数组的一次遍历都不能做，就能完成所有的查找，属我愚笨，不胜惶恐。
如果仅仅是查找过程的话，你的这个复杂度，是不是有点宽裕了。好多东西都可以用呀。。。
PS：（我还真是第一次看见SPRT（N）的时间复杂度。。。LG（N）倒是勉强见过几次）
wantdrink 2009-08-13
- 打赏
- 举报
查找先要排序
即便不查找排一下都nlgn了，或者知道数据上限最快也要O(n)，还没开始查找，这个O(sqrt(n))是考官刁难你吗？
可能是楼主对题目的描述不是考官最初的意思吧
即便不查找排一下都nlgn了，或者知道数据上限最快也要O(n)，还没开始查找，这个O(sqrt(n))是考官刁难你吗？
可能是楼主对题目的描述不是考官最初的意思吧
我看你有戏 2009-08-12
- 打赏
- 举报
[Quote=引用 8 楼 huangjunjie_1985 的回复:]
比如说int a[] = {1, 3, 5, 6, 7 , 9}
int b[] = {3, 6}
返回int c[] = {1, 3}表示3在数组a的第一位，6在数组a的第三位。
[/Quote]
已经排序的话就好说了啊，比如找到在a数组中找到b[0]了，那就接下去找b[1],一步步下去就好了
比如说int a[] = {1, 3, 5, 6, 7 , 9}
int b[] = {3, 6}
返回int c[] = {1, 3}表示3在数组a的第一位，6在数组a的第三位。
[/Quote]
已经排序的话就好说了啊，比如找到在a数组中找到b[0]了，那就接下去找b[1],一步步下去就好了
huntzw 2009-08-12
- 打赏
- 举报
[Quote=引用 25 楼 silwoods 的回复:]
假如要在B数组中找A数组中的所有数，即A全在B中。记作A[s]和B[m]
1、将两个数组都先按相同的顺序排序，比如都是从小到大，或者都是从大到小。
2、取A的第一个数A[1]，用二分法在B中找到A[1]，即比较A[1]和B[m/2]的大小，如果A[1]大，则比较A[1]和B[m/2]到B[m]中间的那个数，即B[(m+m/2)/2]。依次类推，可以找到A[1]在B中的位置，假设是n。
3、从A[2]开始，在B中找的时候就不用从B[1]到B[m]整个用二分法找了。因为A也是排序的，A[2]一定比A[1]大，所以A[2]一定在B[n]的后面，只需要在B[n]到B[m]之间找就行了。
依次类推即可。
[/Quote]
我觉得面试官可能是这个意思！
假如要在B数组中找A数组中的所有数，即A全在B中。记作A[s]和B[m]
1、将两个数组都先按相同的顺序排序，比如都是从小到大，或者都是从大到小。
2、取A的第一个数A[1]，用二分法在B中找到A[1]，即比较A[1]和B[m/2]的大小，如果A[1]大，则比较A[1]和B[m/2]到B[m]中间的那个数，即B[(m+m/2)/2]。依次类推，可以找到A[1]在B中的位置，假设是n。
3、从A[2]开始，在B中找的时候就不用从B[1]到B[m]整个用二分法找了。因为A也是排序的，A[2]一定比A[1]大，所以A[2]一定在B[n]的后面，只需要在B[n]到B[m]之间找就行了。
依次类推即可。
[/Quote]
我觉得面试官可能是这个意思！
Steel1010 2009-08-12
- 打赏
- 举报
就两分查找本身O(logn)是远小于O（sqrt（n））的，在此仅考虑折半查找算法本身
#define MAX 100
int n = 0;
int x[MAX];//seq data array {x[0]< ... x[max - 1]}
int binary(int t)
{
int l, u;
if（x[0] > ｔ ｜｜x[n] < t || n < 0）{
printf("input error \n");
return -1;
}
l = 0;
u = n;
while (l <= m) {
m = (l + u) / 2;
if (x[m] < t) {
l = m + 1;
} else if (x[m] > t) {
u = m - 1;
} else { //find it
return m;
}
}
return -1;
}
int p[MAX]; //用于检验的数组顺序是打乱的
int main(void)
{
int i = 0;
printf("please input n(<%d)", MAX);
scanf("%d", &n);
for (i = 0; i < n；i++) {
if (-1 == binary(p[i])) {
printf("fail to find p[%d] = %d \n", i, p[%d]);
}
}
}
#define MAX 100
int n = 0;
int x[MAX];//seq data array {x[0]< ... x[max - 1]}
int binary(int t)
{
int l, u;
if（x[0] > ｔ ｜｜x[n] < t || n < 0）{
printf("input error \n");
return -1;
}
l = 0;
u = n;
while (l <= m) {
m = (l + u) / 2;
if (x[m] < t) {
l = m + 1;
} else if (x[m] > t) {
u = m - 1;
} else { //find it
return m;
}
}
return -1;
}
int p[MAX]; //用于检验的数组顺序是打乱的
int main(void)
{
int i = 0;
printf("please input n(<%d)", MAX);
scanf("%d", &n);
for (i = 0; i < n；i++) {
if (-1 == binary(p[i])) {
printf("fail to find p[%d] = %d \n", i, p[%d]);
}
}
}
折shui 2009-08-12
- 打赏
- 举报
算法，还要研究
lijian3256 2009-08-12
- 打赏
- 举报
貌似上次哪里看到强力算法..
v_name 2009-08-12
- 打赏
- 举报
如果是无序的，哪用二分法去查有什么用了，
二分法主要是用在有序的情况下，先找到最中间的哪个再比较大小，这样就能切一片去了。减少了数据的查询次数。
二分法主要是用在有序的情况下，先找到最中间的哪个再比较大小，这样就能切一片去了。减少了数据的查询次数。
showjim 2009-08-11
- 打赏
- 举报
[Quote=引用楼主 huangjunjie_1985 的回复:]
有两个int数组，一个数组的每个元素都存在于另一个数组中，要求在O(sqrt(n))情况下，找出一个数组中每个元素在另一个数组中的位置。
面试官提示用二分查找，把整个数组合在一起做二分查找，小弟无能，没有做出来。不知道哪位高手能不能解答一下？
[/Quote]
可能是要你定义这两个数组的结构与关系,达到O(sqrt(n))的要求;否则就是暗示不要你.
有两个int数组，一个数组的每个元素都存在于另一个数组中，要求在O(sqrt(n))情况下，找出一个数组中每个元素在另一个数组中的位置。
面试官提示用二分查找，把整个数组合在一起做二分查找，小弟无能，没有做出来。不知道哪位高手能不能解答一下？
[/Quote]
可能是要你定义这两个数组的结构与关系,达到O(sqrt(n))的要求;否则就是暗示不要你.
zyq5945 2009-08-11
- 打赏
- 举报
mark
lx_ing 2009-08-11
- 打赏
- 举报
将第数组A 先排序（nlogn）；
再把数组B中每个元素 依次用折半查找 ，找其在有序的数组A中的位置（mlogn），并记录当前B元素的序号 即是要求的位置。
总的应该是nlogn+mlogn吧
再把数组B中每个元素 依次用折半查找 ，找其在有序的数组A中的位置（mlogn），并记录当前B元素的序号 即是要求的位置。
总的应该是nlogn+mlogn吧
macrojj 2009-08-11
- 打赏
- 举报
MARK
task555 2009-08-11
- 打赏
- 举报
二分法查找时间复杂度为O(sqrt(n))但前提是在有序数组中进行查找。
如果要在一个有序数组中查一个无序数组的数据应该是O(nsqrt(n))不可能是O(sqrt(n))
如果是在一个有序数组中查找另一个有序数组，才有可能O(sqrt(n))
如果要在一个有序数组中查一个无序数组的数据应该是O(nsqrt(n))不可能是O(sqrt(n))
如果是在一个有序数组中查找另一个有序数组，才有可能O(sqrt(n))
fiveyes 2009-08-11
- 打赏
- 举报
这可能是一个描述的问题。
实际上楼主觉得28楼的描述似乎比楼主的描述更接近面试官的描述……
实际上楼主觉得28楼的描述似乎比楼主的描述更接近面试官的描述……
tangtao0308 2009-08-11
- 打赏
- 举报
不知道对不对，请大家讨论。
tangtao0308 2009-08-11
- 打赏
- 举报
我来说一说，
A[n]B[m]其中m<n，B中的数据全部在A中，A为有序的。
x=0;
index=0;
astart=0;
aend=n;
for(x=0;x<m;x++)
{
if(x!=0)
{
if(B[x-1]>B[x])
{
astart=0;
aend=index;
}else
{
astart=index;
aend=n;
}
}
B[x]在A中,二分查找.得出结果B在A的位置index;
}
A[n]B[m]其中m<n，B中的数据全部在A中，A为有序的。
x=0;
index=0;
astart=0;
aend=n;
for(x=0;x<m;x++)
{
if(x!=0)
{
if(B[x-1]>B[x])
{
astart=0;
aend=index;
}else
{
astart=index;
aend=n;
}
}
B[x]在A中,二分查找.得出结果B在A的位置index;
}
Victor_Dinho 2009-08-10
- 打赏
- 举报
假如A数组的元素个数是m，B数组的元素个数是n，那么复杂度应该是O(mlogn)啊~~不知道O(sqrt(n))怎么来的~~
加载更多回复（33）
