现在的位置: 首页 > 综合 > 正文

关于二分查找的面试题归类

2014年01月05日 ⁄ 综合 ⁄ 共 3751字 ⁄ 字号 小 中 大 ⁄ 评论关闭

转自http://blog.csdn.net/walkinginthewind/article/details/8937978

二分查找，最基本的算法之一，也是面试中常被考察的重点，因为基本的算法最能反映出一个人的基础是否扎实。本文对二分查找相关题目做一个总结。

题目列表：

1. 给定一个有序（非降序）数组A，求任意一个i使得A[i]等于target，不存在则返回-1
2. 给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1
3. 给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1
4. 给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]小于target，不存在则返回-1
5. 给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]大于target，不存在则返回-1
6. 给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数。
7. 给定一个有序（非降序）数组A，若target在数组中出现，返回位置，若不存在，返回它应该插入的位置。
8. 给定一个有序（非降序）数组A，可含有重复元素，求绝对值最小的元素的位置
9. 给定一个有序（非降序）数组A和一个有序（非降序）数组B，可含有重复元素，求两个数组合并结果中的第k(k>=0)个数字。
10. 一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求target在变化后的数组中出现的位置，不存在则返回-1.
11. 一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求最小值所在位置
12. 一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求第k(k > 0)小元素

1. 给定一个有序（非降序）数组A，求任意一个i使得A[i]等于target，不存在则返回-1
这个是最原始的二分查找题目，利用数组的有序特性，拆半查找，使得查找时间复杂度为O(logN)。请参考实现代码与注释。

[cpp] view
plaincopy

  1. int search(int A[], int n, int target)  
  2. {  
  3.     int low = 0, high = n-1;  
  4.     while(low <= high)  
  5.     {  
  6.         // 注意：若使用(low+high)/2求中间位置容易溢出  
  7.         int mid = low+((high-low)>>1);   
  8.         if(A[mid] == target)  
  9.             return mid;  
  10.         else if(A[mid] < target)  
  11.             low = mid+1;  
  12.         else // A[mid] > target  
  13.             high = mid-1;  
  14.     }  
  15.     return -1;  
  16. }  

2. 给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1
此题也就是求target在数组中第一次出现的位置。这里可能会有人想先直接用原始的二分查找，如果不存在直接返回-1，如果存在，然后再顺序找到这个等于target值区间的最左位置，这样的话，最坏情况下的复杂度就是O（n）了，没有完全发挥出二分查找的优势。这里的解法具体过程请参考实现代码与注释。

[cpp] view
plaincopy

  1. int searchFirstPos(int A[], int n, int target)  
  2. {  
  3.     if(n <= 0) return -1;  
  4.     int low = 0, high = n-1;  
  5.     while(low < high)  
  6.     {  
  7.         int mid = low+((high-low)>>1);  
  8.         if(A[mid] < target)  
  9.             low = mid+1;  
  10.         else // A[mid] >= target  
  11.             high = mid;  
  12.     }  
  13.     /*  
  14.     循环过程中，当low大于0时，A[low-1]是小于target的，因为A[mid] < target时， 
  15.     low=mid+1；当high小于n-1时，A[high]是大于等于target的，因为A[mid] >= target时， 
  16.     high = mid；循环结束时，low 等于 high，所以，如果A[low](A[high])等于target， 
  17.     那么low(high)就是target出现的最小位置，否则target在数组中不存在。 
  18.     */  
  19.     if(A[low] != target)  
  20.         return -1;  
  21.     else  
  22.         return low;  
  23. }  

3. 给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1

此题也就是求target在数组中最后一次出现的位置。与上一题基本一样，但是有个地方要注意，具体请参考实现代码与注释。

[cpp] view
plaincopy

  1. int searchLastPos(int A[], int n, int target)  
  2. {     
  3.     if(n <= 0) return -1;  
  4.     int low = 0, high = n-1;  
  5.     while(low < high)  
  6.     {  
  7.         /* 
  8.         这里中间位置的计算就不能用low+((high-low)>>1)了，因为当low+1等于high 
  9.         且A[low] <= target时，会死循环；所以这里要使用low+((high-low+1)>>1)， 
  10.         这样能够保证循环会正常结束。 
  11.         */  
  12.         int mid = low+((high-low+1)>>1);  
  13.         if(A[mid] > target)  
  14.             high = mid-1;  
  15.         else // A[mid] <= target  
  16.             low = mid;  
  17.     }  
  18.     /*  
  19.     循环过程中，当high小于n-1时，A[high+1]是大于target的，因为A[mid] > target时， 
  20.     high=mid-1；当low大于0时，A[low]是小于等于target的，因为A[mid] <= target时， 
  21.     low = mid；循环结束时，low 等于 high，所以，如果A[high](A[low])等于target， 
  22.     那么high(low)就是target出现的最大位置，否则target在数组中不存在。 
  23.     */  
  24.     if(A[high] != target)  
  25.         return -1;  
  26.     else  
  27.         return high;  
  28. }  

4. 给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]小于target，不存在则返回-1。

也就是求小于target的最大元素的位置。请参考实现代码与注释。

[cpp] view
plaincopy

  1. int searchLastPosLessThan(int A[], int n, int target)  
  2. {  
  3.     if(n <= 0) return -1;  
  4.     int low = 0, high = n-1;  
  5.     while(low < high)  
  6.     {  
  7.         int mid = low+((high-low+1)>>1); // 注意，不要导致死循环  
  8.         if(A[mid] < target)  
  9.             low = mid;  
  10.         else // A[mid] >= target  
  11.             high = mid-1;  
  12.     }  
  13.     /*  
  14.     循环过程中，当low大于0时，A[low]是小于target的，因为A[mid] < target时， 
  15.     low=mid；当high小于n-1时，A[high+1]是大于等于target的，因为A[mid] >= target时， 
  16.     high = mid-1；循环结束时，low 等于 high，所以，如果A[low](A[high])小于target， 
  17.     那么low(high)就是要找的位置，否则不存在这样的位置（A[0] >= target时）。 
  18.     */  
  19.     return A[low] < target ? low : -1;  
  20. }  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞