程序员人生 网站导航

去哪网2015年春季校园招聘笔试题

栏目:php教程时间:2015-05-19 07:58:51
请实现以下函数 int indexOf(int []array ,int x),给定1个循环有序的数组,请在这个数组中找到指定元素,找到的话返回下表,没有找到返回⑴.该数组的特点是1个单调递增的数组向右循环移位构成的.举例说明,原数组是{4,8,13,20,23,34,41,52}.经过向右循环移位构成的数组多是{23,34,41,52,4,8,13,20}或{4,8,13,20,23,34,41,52}.

刚拿到题目觉得太简单,循环1边每一个判断是不是等于x,如果等于返回下表,否则返回⑴.可是我们不知道数组的大小,这个时候我机灵的想到了以下代码。

#include <iostream> using namespace std; int main() { int a[]={1,2,3,4,5,6,7,8,9,10}; int n=sizeof(a)/sizeof(int); printf("%d ",n); return 0; }

上面代码中数组大小没有给出,用sizeof可以正确计算出数组的大小,下面的代码就显得瓜熟蒂落了.

#include <iostream> using namespace std; int indexOf(int a[],int x) { int n=sizeof(a)/sizeof(int); for (int i = 0; i < n; ++i) { if(a[i]==x) return i; } return ⑴; } int main() { int a[10]={10,1,2,3,4,5,6,7,8,9}; printf("%d ",indexOf(a,3)); }

当我们运行代码时发现打印了⑴,为何代码不能依照预期的运行呢?

在函数传递的进程中,参数表中的数组将退化为指向该数组元素类型的指针,代码中的数组大小难以求出,看以下例子.

#include <iostream> using namespace std; int indexOf(int a[],int x) { int n=sizeof(a)/sizeof(int); printf("%d ",n); printf("%d ",sizeof(int)); return 0; } int main() { int a[10]={1,2,3,4,5,6,7,8,9,10}; indexOf(a,5); return 0; }

在我电脑上运行结果显示sizeof(a)是数组a首地址所占字节数,sizeof(int)是int类型所占字节数.
那末这道题看语法应当是C#,数组长度不是关注点,重点是利用2分查找改进算法int binarysearch(int *a ,int n, int x)来完成.

#include <iostream> using namespace std; int binarysearch(int *a ,int n, int x) { int low = 0, high = n - 1; while(low < high) { int mid = (low + high)/2; if(a[low] == x) return low; if(a[high] == x) return high; if(a[mid] == x) return mid; if(a[mid] > a[low] ) { if( x > a[low] && x < a[mid]) high = mid⑴ ; else low = mid+1 ; } else if(a[mid] < a[high]) { if( x > a[mid] && x < a[high]) low = mid+1 ; else high = mid⑴ ; } else { if (x != a[mid]) return ⑴; else return mid; } } return ⑴; } int main() { int a[8] = {23,34,41,52,4,8,13,20}; int index = binarysearch(a,8,41); cout<< index << endl; return 0; }




------分隔线----------------------------
------分隔线----------------------------

最新技术推荐