二分查找法的实现和应用(进阶篇)
<div id="cnblogs_post_body">在《二分查找法的实现和应用汇总》中，我介绍了二分查找法的基本应用，不过在面试的准备过程中，我还碰到了更多对于二分查找法的更进一步的使用。其实在《二分查找法的实现和应用汇总》的最后，我已经介绍了一个非常规的使用，也就是基于&ldquo;轮转后的有序数组（Rotated Sorted Array）&rdquo;检查某一个数是否存在。找到轮转后的有序数组中第K小的数
对于普通的有序数组来说，这个问题是非常简单的，因为数组中的第K-1个数（即A）就是所要找的数，时间复杂度是O(1)常量。但是对于轮转后的有序数组，在不知道轮转的偏移位置，我们就没有办法快速定位第K个数了。
不过我们还是可以通过二分查找法，在log(n)的时间内找到最小数的在数组中的位置，然后通过偏移来快速定位任意第K个数。当然此处还是假设数组中没有相同的数，原排列顺序是递增排列。
在轮转后的有序数组中查找最小数的算法如下：
<div class="cnblogs_code">//return the index of the min value in the Rotated Sorted Array, whose range is int findIndexOfMinVaule(int A[], int low, int high){ if (low > high) return -1; while (low < high) { int mid = (low + high)/2; if (A > A) low = mid +1; else high = mid; } //at this point, low is equal to high return low;}
页:
[1]