二分查找是面试中手写代码经常遇到的题目, 昨天还有同事说有个面试, 手写代码这一环节就是二分查找.
在下面两个版本的实现中, 假设传入的数组是递增的.
在面试的时候, 需要问清楚, 传入的数组的特点:
- 是否是排好序的
- 递增还是递减
- 当数字有重复时, 是否返回任意一个数的下标即可
- 同时, 查找时需要特别注意边界条件
二分查找实现起来不算难, 需要特别注意这些细节. 正是这些细节决定了你是否可以通过面试的这个环节.
Case 1: 二分查找一个数的下标, 当有多个目标数存在时,返回任意一个.
递归版本
int BinarySearch::search(const std::vector<int>& datas,
const int dest)
{
LOG(INFO) << "Enter: " << __func__;
int ret = -1;
ret = searchInternal(datas, 0, datas.size() - 1, dest);
LOG(INFO) << "Leave: " << __func__;
return ret;
}
int BinarySearch::searchInternal(const std::vector<int>& datas,
const int startIndex,
const int endIndex,
const int dest)
{
if (startIndex > endIndex)
{
LOG(INFO) << "Not Found Dest: " << dest;
return -1;
}
int mid = startIndex + (endIndex - startIndex) / 2;
if (datas[mid] == dest)
{
return mid;
}
else if (datas[mid] > dest)
{
return searchInternal(datas, startIndex, mid - 1, dest);
}
else
{
return searchInternal(datas, mid + 1, endIndex, dest);
}
}
非递归版本
只实现了internal方法
int BinarySearch::searchInternal(const std::vector<int>& datas,
int startIndex,
int endIndex,
const int dest)
{
int ret = -1;
while (startIndex <= endIndex)
{
int midIndex = startIndex + (endIndex - startIndex) / 2;
if (datas[midIndex] == dest)
{
ret = midIndex;
break;
}
else if (datas[midIndex] < dest)
{
startIndex = midIndex + 1;
}
else
{
endIndex = midIndex - 1;
}
}
return ret;
}
Case 2: 查找第一个大于或等于某个数的下标
算法思想: 等待查找失败,那么查找失败的最后一个区间的下一个元素, 即是满足条件的元素.
例如:
数组: 1 2 3 5 6 7
目标数: 4
查找区间的起始index和结束index的变化见下表
| 查找轮数 | startIndex | endIndex |
|---|---|---|
| 1 | 0 | 5 |
| 2 | 0 | 2 |
| 3 | 1 | 2 |
| 4 | 2 | 2 |
| 5 | 3 | 2 |
结束时, startIndex所指的即为满足条件的元素下标.
需要注意的是, 最后返回的时候,需要比较startIndex和最初endIndex的大小,如果 startIndex > endIndex, 说明查找失败,没有满足条件的元素.
实现
int BinarySearch::searchInternal(const std::vector<int>& datas,
int startIndex,
int endIndex,
const int dest)
{
int ret = -1;
int end = endIndex;
while (startIndex <= endIndex)
{
int midIndex = startIndex + (endIndex - startIndex) / 2;
if (datas[midIndex] >= dest)
{
endIndex = midIndex - 1;
}
else
{
startIndex = midIndex + 1;
}
}
return startIndex <= end ? startIndex : -1;
}
Case 3: 查找第一个大于某个数的下标
当中间下标数小于等于目标数时, 继续查找右边区间.
当中间下标数大于目标数时, 继续查找左边区间.
当startIndex > endIndex时, 结束查找, 此时startIndex所指的数字即为查找的数字下标, 如果startIndex大于起始endIndex则查找失败,返回 -1.
int BinarySearch::searchInternal(const std::vector<int>& datas,
int startIndex,
int endIndex,
const int dest)
{
int ret = -1;
int end = endIndex;
while (startIndex <= endIndex)
{
int midIndex = startIndex + (endIndex - startIndex) / 2;
if (datas[midIndex] > dest)
{
endIndex = midIndex - 1;
}
else
{
startIndex = midIndex + 1;
}
}
return startIndex <= end ? startIndex : -1;
}
扩展题型
扩展1: 查找数组中某个数的位置的最小下标, 没有则返回-1
思路参考Case 2. 先找到第一个大于或者等于目标数的数字, 判断该数字是否等于目标数, 如果等于目标数, 则返回该数字的下标, 否则返回-1.
扩展2: 查找数组中某个数的位置的最大下标, 没有则返回-1
思路参考Case 3. 先找到第一个大于目标数的数字, 判断该数字前面一个下标的数字是否等于目标数, 如果等于目标数, 则返回该数字的下标, 否则返回-1.
扩展3: 查找数组中小于某个数的最大下标, 没有返回-1.
思路参考Case 2. 先找到第一个大于或者等于目标数的数字, 然后判断前一个下标是否合法, 如果合法,则返回, 否则返回-1.
扩展4: 查找数组中某个数的出现次数
思路: 使用Case 2求出下界, 使用Case 3求出上界, 然后用上界 - 下界 即为某个数出现的次数.
但是需要注意返回值, 当越界时, 不能返回-1, 而是返回越界值来计算差值.
参考资料:
http://blog.csdn.net/yefengzhichen/article/details/52372407
