二分查找的变种

  1.给定一个数组,其值先从小到大递增后从大到小递减,找出最大的值。eg:{1,2,5,6,4,2,1}  -> 6

  2.“轮转后的有序数组(Rotated Sorted Array)”,现有一特殊数组A[],它是循环递增的,eg: 如A[]={ 17 19 20 25 1 4 7 9},试在这样的数组中找一元素x,看看是否存在。

  3.找到轮转后的有序数组中第K小的数

  4.整数的求平方根函数

  其实这个问题用数学的表达方式就是:对于非负整数x,找出另一个非负整数n,其中n满足 n^2 <= x < (n+1)^2。

  5.有两个已排好序的数组A和B,长度分别为n,m,找出两个有序数组中第K个数,要求时间代价为O(logn+logm)。

  6.在多个服务器上每个服务器都有一批数,每个服务器直接并不知道对方的内容,你有一个主机可以联到每个服务器上去请求数据,现在要求从这些服务器的数据中找出第K小的数。(上题扩展)

原文地址:https://www.cnblogs.com/jslee/p/3446516.html