二分查找_二分查找 java_二分查找最多比较次数(3)

当然在这个问题上，还有其它好的算法，这里只是想借次来指出二分查找法的应用。

之前已经介绍了二分查找法的不少内容。下边，我还想再讲讲碰到的一些面试题目中可用二分查找法的题目。不过这些都是基于“找出两个有序数组中第K个数”的扩展问题。

其实这个问题还是假设数组中不会有相同的值，直观的解法也是O(m+n)的遍历。网上有很多的解答方法（可见文后引用），不过都存在一定问题。该问题主要出在中数(Median)的计算方式上：

如果数组有个数是奇数，那么中数的值就是有序时处于中间的数；如果数组个数是偶数的，那么就是有序时中间两个数平均时。

网上的解法，有些假定两个数组相同长度，因此不具有一般性；另一种解法，则是针对两种情况做出不同的解法。

其实参照“找出两个有序数组中第K个数”，我们又已经两个数组的长度，其实就已经知道我们要找的数其实是第(m+n)/2 + 1个数（奇数时）或者是第(m+n)/2 和第(m+n)/2 + 个数（偶数时）。即使是调用两次，复杂度也依然是O(log(m+n))。

问题的描述是这样的：在多个服务器上每个服务器都有一批数，每个服务器直接并不知道对方的内容，你有一个主机可以联到每个服务器上去请求数据，现在要求从这些服务器的数据中找出第K小的数。

一个常用的方法就是在主机上创建一个存储K个数据堆结构然后获取每个服务器的数据并与堆中数据进行比较和交换。最后我们就可以得到所要的数据。

该问题其实可视为是“找出两个有序数组中第K个数”的多服务器变体。二分查找一般诸如Google，Facebook，Microsoft这样的大公司会比较喜欢问（我有个朋友面试FB时就问到了这个问题）。

问题并没有表明每个服务器下的数是否有序的，不过我们可以让每个服务器对自己的数据进行排序，这是同步的，所以最多是O(n log n)的时间。在主机上则维护一个K大的有序数组，然后于每个服务器之间进行进行“找出两个有序数组中第K个数”，之后保留下新的前K个数。其复杂度应该是O(n log k)，其中n是服务器数量，k是所求目标。加上服务器排序时间，基本可以维持在O(n log n)的级别。

Find the k-th Smallest Element in the Union of Two Sorted Arrays – LeetCode

Binary Search to Compute Square root (Java) – StackOverflow

Median of two sorted arrays – GeeksforGeeks

Median of Two Sorted Arrays –LeetCode

Microsoft Interview Question – CareerCup

Find the largest k numbers in k arrays stored across k machines – StackOverflow

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-30980-3.html