昨天面试的一道上机笔试题,哪位朋友有好的思路吗?

BuTa丶潇

回复 3# bruceteen


    你好,我用了这个函数,可是有个别地方不是太懂,网上看了下手册,还是有个别地方不太明白。
比如:
int a=3;
vector<double> nums;
nums.push_back(1.5);
nums.push_back(2.6);
nums.push_back(3.7);
pair<vector<double>::iterator,vector<double>::iterator> range;
range = equal_range(nums.begin(),nums.end(),a);

cout<<*range_a.first<<endl;//得到3.7

这里我有一点不太清楚怎么操作..就是我得到的是3.7，但是我实际想得到的是"2"这个下标(这里把向量容器比喻成数组)。
请问有什么办法得到“2”这个下标呢。我查了网上的一些资料没找到。。
是需要再做一次遍历吗？遍历比较麻烦，请问有其他办法吗？

anqiu1987

我感觉2分法就行啊，如果中间数在a，b之间，那在左边找a在右边找b，如果小于a，在右边找，小于b在左边找嘛

cxqphysics

设数组为A对其保存一个排好序的副本，并在副本里保存一个附加数据，用来表示其在原数组A中的位置，对于给出的区间[a,b]，二分找出区间的两端在副本中的位置c d，遍历c d之间的元素，就可以找出在[a,b]中的元素在A中的位置

wlmouse

回复 14# pmerofc


    是不让你a++到b，然后二分查找做的限制。

shan_ghost

wlmouse 发表于 2013-04-03 18:49

直接二分查找a，然后二分查找b。

浮点数只是不能比较相等而已。稍微改良下二分查找算法，找“第一个大于等于a的数字的序号”和“第一个小于等于b的数字的序号”，还不是小菜一碟。


这道题考的是对二分查找算法的掌握程序，以及对知识灵活运用的能力。

wlmouse

回复 16# shan_ghost


    是我想错了吗？好像确实是想多了。

DKDouzi

围观，自己对算法没多少信心。

flfq

这题应不是考的算法吧
而是考的底层知识，比如指针的运用

按理最多移动30次就可以得到结果，一点都不占资源的，几微秒的时间而已

根本用不到递归

我怀疑出题是个学汇编的