二分查找

版权所有,转载请注明出处,谢谢!http://blog.csdn.net/walkinginthewind/article/details/8937978

版权所有,转载请注明出处,谢谢! http://blog.csdn.net/walkinginthewind/article/details/8937978

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

题目列表:

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. }  

5. 给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]大于target,不存在则返回-1。 也就是求大于target的最小元素的位置。请参考实现代码与注释。

[cpp] view plaincopy

  1. int searchFirstPosGreaterThan(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.             high = mid;  
  10. else // A[mid] <= target
  11.             low = mid+1;  
  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[high](A[low])大于target,
  17.     那么high(low)就是要找的位置,否则不存在这样的位置(A[n-1] <= target时)。
  18.     */
  19. return A[high] > target ? high : -1;  
  20. }  

6. 给定一个有序(非降序)数组A,可含有重复元素,求target在数组中出现的次数

求出第一次出现位置和最后一次出现位置。由于前面都已实现,这里不多解释。请参考实现代码与注释

[cpp] view plaincopy

  1. int count(int A[], int n, int target)  
  2. {  
  3. int firstPos = searchFirstPos(A, n, target); // 第一次出现位置
  4. if(firstPos == -1)  
  5. return 0;  
  6. int lastPos = searchLastPos(A, n, target);  // 最后一次出现位置
  7. return lastPos-firstPos+1;  // 出现次数
  8. }  

此题描述或者改为求目标值在数组中的索引范围。

7. 给定一个有序(非降序)数组A,若target在数组中出现,返回位置,若不存在,返回它应该插入的位置

如    [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0

[cpp] view plaincopy

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

8. 给定一个有序(非降序)数组A,可含有重复元素,求绝对值最小的元素的位置

找第一个大于等于0的位置,然后和前一个元素的绝对值比较,返回绝对值较小的元素的位置。请参考实现代码与注释

[cpp] view plaincopy

  1. int searchMinAbs(int A[], int n)  
  2. {  
  3. int low = 0, high = n-1;  
  4. while(low < high)  
  5.     {  
  6. int mid = low+((high-low)>>1);  
  7. if(A[mid] < 0)  
  8.             low = mid+1;  
  9. else // A[mid] >= 0
  10.             high = mid;  
  11.     }  
  12. /* 循环结束时,如果low != n-1,A[low] >= 0,如果low>0,A[low-1] < 0 */
  13. if(low > 0 && abs(A[low-1]) < abs(A[low]))  
  14. return low-1;  
  15. else
  16. return low;  
  17. }  

9. 给定一个有序(非降序)数组A和一个有序(非降序)数组B,可含有重复元素,求两个数组合并结果中的第k(k>=0)个数字。

这个题目出现了两个数组,有序的,不管怎样我们就应该首先考虑二分查找是否可行。若使用顺序查找,时间复杂度最低为O(k),就是类似归并排序中的归并过程。使用用二分查找时间复杂度为O(logM+logN)。二分查找的具体实现过程请参考实现代码与注释。

[cpp] view plaincopy

  1. int findKthIn2SortedArrays(int A[], int m, int B[], int n, int k)  
  2. {  
  3. if(m <= 0) // 数组A中没有元素,直接在B中找第k个元素
  4. return B[k];  
  5. if(n <= 0) // 数组B中没有元素,直接在A中找第k个元素
  6. return A[k];  
  7. int i = (m-1)>>1; // 数组A的中间位置
  8. int j = (n-1)>>1; // 数组B的中间位置
  9. if(A[i] <= B[j])  // 数组A的中间元素小于等于数组B的中间元素
  10.     {  
  11. /*
  12.         设x为数组A和数组B中小于B[j]的元素数目,则i+1+j+1小于等于x,
  13.         因为A[i+1]到A[m-1]中还可能存在小于等于B[j]的元素;
  14.         如果k小于i+1+j+1,那么要查找的第k个元素肯定小于等于B[j],
  15.         因为x大于等于i+1+j+1;既然第k个元素小于等于B[j],那么只
  16.         需要在A[0]~A[m-1]和B[0]~B[j]中查找第k个元素即可,递归调用下去。
  17.         */
  18. if(k < i+1+j+1)  
  19.         {  
  20. if(j > 0)  
  21. return findKthIn2SortedArrays(A, m, B, j+1, k);  
  22. else // j == 0时特殊处理,防止死循环
  23.             {  
  24. if(k == 0)  
  25. return min(A[0], B[0]);  
  26. if(k == m)  
  27. return max(A[m-1], B[0]);  
  28. return A[k] < B[0] ? A[k] : max(A[k-1], B[0]);  
  29.             }  
  30.         }  
  31. /*
  32.         设y为数组A和数组B中小于于等于A[i]的元素数目,则i+1+j+1大于等于y;
  33.         如果k大于等于i+1+j+1,那么要查找到第k个元素肯定大于A[i],因为
  34.         i+1+j+1大于等于y;既然第k个元素大于A[i],那么只需要在A[i+1]~A[m-1]
  35.         和B[0]~B[n-1]中查找第k-i-1个元素,递归调用下去。
  36.         */
  37. else
  38. return findKthIn2SortedArrays(A+i+1, m-i-1, B, n, k-i-1);  
  39.     }   
  40. // 如果数组A的中间元素大于数组B的中间元素,那么交换数组A和B,重新调用即可
  41. else
  42. return findKthIn2SortedArrays(B, n, A, m, k);  
  43. }  

10. 一个有序(升序)数组,没有重复元素,在某一个位置发生了旋转后,求target在变化后的数组中出现的位置,不存在则返回-1

如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2

我们先比较中间元素是否是目标值,如果是返回位置。如果不是,我们就应该想办法将搜索区间减少一半。因为存在旋转变化,所以我们要多做一些判断。我们知道因为只有一次旋转变化,所以中间元素两边的子数组肯定有一个是有序的,那么我们可以判断target是不是在这个有序的子数组中,从而决定是搜索这个子数组还是搜索另一个子数组。具体请参考实现代码与注释。

[cpp] view plaincopy

  1. int searchInRotatedArray(int A[], int n, int target)   
  2. {  
  3. int low = 0, high = n-1;  
  4. while(low <= high)  
  5.     {  
  6. int mid = low+((high-low)>>1);  
  7. if(A[mid] == target)   
  8. return mid;  
  9. if(A[mid] >= A[low])   
  10.         {  
  11. // low ~ mid 是升序的
  12. if(target >= A[low] && target < A[mid])  
  13.                 high = mid-1;  
  14. else
  15.                 low = mid+1;  
  16.         }  
  17. else
  18.         {  
  19. // mid ~ high 是升序的
  20. if(target > A[mid] && target <= A[high])  
  21.                 low = mid+1;  
  22. else
  23.                 high = mid-1;  
  24.         }  
  25.     }  
  26. return -1;  
  27. }  

如果这样的数组中存在重复元素,还能使用二分吗?答案是不能。请看几个例子

[1, 2, 2, 2, 2], [2, 1, 2, 2, 2], [2, 2, 1, 2, 2], [2, 2, 2, 1, 2], [2, 2, 2, 2, 1]这些都是有第一个数组旋转一次变化来的,我们不能通过二分确定是否存在元素1.

11. 一个有序(升序)数组,没有重复元素,在某一个位置发生了旋转后,求最小值所在位置

如果中间元素小于左端元素,则最小值在左半区间内(包含中间元素);如果中间元素大于右端元素,则最小值在右半区间内(包含中间元素)。请参考实现代码与注释。

[cpp] view plaincopy

  1. int searchMinInRotatedArray(int A[], int n)   
  2. {  
  3. if(n == 1)  
  4. return 0;  
  5. int low = 0, high = n-1;  
  6. while(low < high-1) // 保证mid != low且mid != high
  7.     {  
  8. int mid = low+((high-low)>>1);  
  9. if(A[mid] < A[low]) // 最小值在low~mid
  10.             high = mid;  
  11. else // A[mid] > A[low], // 最小值在mid和high之间
  12.             low = mid;  
  13.     }  
  14. return A[low] < A[low+1] ? low : low+1;  
  15. }  

12. 一个有序(升序)数组,没有重复元素,在某一个位置发生了旋转后,求第k(k > 0)小元素的位置 我们可以利用上一题的解答,求出最小值所在位置后,便可以求出第k小元素。请参考实现代码与注释

[cpp] view plaincopy

  1. int searchKthInRotatedArray(int A[], int n, int k)   
  2. {  
  3. int posMin = searchMinInRotatedArray(A, n);  
  4. re

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Pythonista

Go 语言数据类型

数据类型的出现是为了把数据分成所需内存大小不同的数据,编程的时候需要用大数据的时候才需要申请大内存,就可以充分利用内存。

681
来自专栏一“技”之长

分分钟使用正则表达式 原

        从概念上来说,正则表达式也是一门小巧而精炼的语言,它可以用来简化检索特定的字符串,替换特定字符等功能,有许多开发语言工具,都内嵌支持正则表达式。...

773
来自专栏编程

判断字符长度小技巧

很多人在判断字符长度的时候总会有一些疑问,到底这个算不算字符,各种转义字符,十进制,十六进制等等。这里教大家一些判断的小技巧: C语言——字符串长度的计算方法 ...

19410
来自专栏前端知识分享

第203天:js---Array对象常用方法

942
来自专栏PHP实战技术

你应该这个姿势学习PHP(2)

2、is_array(),is_bool,is_int(),is_integer(),is_numeric(),is_string(),is_object(),...

4076
来自专栏牛客网

知识总结:四个例子理解闭包//例一//例二//例三//例四

/** * 闭包原理 * @date   2017-04-10 14:04:17 * @version 1 */ //理解作用域、作用域链 //内部作用域可以通...

3579
来自专栏塔奇克马敲代码

第2章 变量和基本类型

2074
来自专栏cs

c++那些事儿9.0指针

知识点综述: ---- 指针:地址。 1.0在32位的cpu上,cpu一般由32根地址线组成,所以地址大小为32位 即4byte,同理可得指针大...

3628
来自专栏生信小驿站

python-运算符与表达式

你所编写的大多数语句(逻辑行)都包含了表达式(Expressions)。一个表达式的简单例子便是 2+3。表达式可以拆分成运算符(Operators)与操作数(...

1822
来自专栏python3

python 数据类型

3.23和52.3E-4是浮点数的例子。E标记表示10的幂。在这里,52.3E-4表示52.3 * 10-4。

1612

扫码关注云+社区

领取腾讯云代金券