深入分析二分查找及其变体
少年π 人气:01—一般二分查找
一般的二分查找代码如下：
int search(int A[], int n, int target)
{
int low = 0, high = n-1;
while(low <= high)
{
// 注意：若使用(low+high)/2求中间位置容易溢出
int mid = low+((high-low)>>1);
if(A[mid] == target)
return mid;
else if(A[mid] < target)
low = mid+1;
else // A[mid] > target
high = mid-1;
}
return -1;
}
上面的二分查找非常的朴实，上述二分查找的作用当然就是：找到数组A[]中等于target的元素。但是这个查找元素隐含了一个条件：这个数组的元素是不包含重复元素的。这个限制可以说是非常的大。我们来看一下，假设存在重复元素，按照上述找法，找的是谁
7 7 7 7 8 10;7
即假设我们找7，显然第一次就找到了，这个“7”在A[2]的位置，也就是我们按照上述思路找，能找到。但并不是最开始的7或者结尾的7.
2—找到有重复元素数组第一个索引元素
假设我们要找到最开始的7，应该如何修改代码
呢？
先上代码：
int searchFirstPos(int A[], int n, int target)
{
if(n <= 0) return -1;
int low = 0, high = n-1;
while(low < high)
{
int mid = low+((high-low)>>1);
if(A[mid] < target)
low = mid+1;
else // A[mid] >= target
high = mid;
}
if(A[low] != target)
return -1;
else
return low;
}
这个代码，为何会找到最开始的7呢？我们看看发生了什么
还是：
7 7 7 7 8 10;7
第一次后，high ->A[2]，循环没结束
第二次后，high->A[1],循环没结束
第三次后,high->A[0],循环结束
循环结束条件喂 low == high！
我们再看一个例子：
5 7 7 7 7 8 10;7
第一次后，high ->A[3]，循环没结束
第一次后，high ->A[1]，循环没结束
第三次后，low->A[1]，循环结束。
再看一个例子
2 5 7 8 9 10 12 13 13 14;13
第一次后，low ->A[5]，循环没结束
第二次后，high ->A[7]，循环没结束
第三次后，low ->A[6]，循环没结束
第三次后，low ->A[7]，循环结束
总结：
也就说：找出现的第一个值，其必然结果是low == high的时候，但是为何是第一个，而不是最后一个呢？
这个主要取决于下面这行代码：
else // A[mid] >= target
high = mid;
也就是说即使A[mid] == target，我们也会使得high == target，换句话而言，即使A[high] == target;
我们也会让high向第一个出现查找值的索引位置靠拢！！！
而
if(A[mid] < target)
low = mid+1;
不过仍然是借鉴了传统二分查找的思想，mid的值小了，就让low=mid+1;
真正要指向第一个，要做的就是：让high向第一个靠拢!!!!
3—找到重复元素数组最后一个元素
上述中说到找第一个元素，要让high向第一个靠拢，而这里要找最后一个元素，则要low向最后一个元素靠拢。
先上代码：
int searchLastPos(int A[], int n, int target)
{
if(n <= 0) return -1;
int low = 0, high = n-1;
while(low < high)
{
/*
这里中间位置的计算就不能用low+((high-low)>>1)了，因为当low+1等于high
且A[low] <= target时，会死循环；所以这里要使用low+((high-low+1)>>1)，
这样能够保证循环会正常结束。
*/
int mid = low+((high-low+1)>>1);
if(A[mid] > target)
high = mid-1;
else // A[mid] <= target
low = mid;
}
if(A[high] != target)
return -1;
else
return high;
}
这里需要注意的是下面这行代码：
int mid = low+((high-low+1)>>1);
假设仍然是：
int mid = low+((high-low)>>1);
我们看会发生什么?
以下述序列为例;
1 2 7 7 7 8 9 13;7
第一次：mid->A[3]，low-->A[3]；
第二次：mid->A[5]，high-->A[4]；
第三次：mid->A[3],low->A[3].....而此时low < high,出现死循环；
可以再举出其他例子，但是结果表明，问题总是出现在最后一步，也就是最后一步总有higg-low =1; 且mid一直等于low，这使得循环一直为死循环。
究其原因，是因为：/2导致的向下取整。而high-low+1可以保证向上取整！！！
那我们为何要这么做呢？主要原因在于：
if(A[mid] > target)
high = mid-1;
即，只要A[mid]>target，high的的值总会减小。也就是说，即使我们向上取整，最终也会使得high指向正确的位置，low也会因为向上取整的原因，最终使得low和high收敛到同一个位置（比如low->A[3]=7,high->A[4]=7.），而low则不同，low刷新成mid，但最后一步有可能不收敛，mid的值不再刷新时候，low的值也不刷新，从而导致low和high不会收敛到同一个位置。
4—给定一个有序（非降序）数组A，若target在数组中出现，返回其第一个位置，若不存在，返回它应该插入的位置
我们稍做分析就知道，对于代码：
上述问题1、2、3无论是哪个问题，当找不到target时候，low==high等于target应该处于的位置是恒成立的。因此，这道题的代码：
int searchPos(int A[], int n, int target)
{
if(n <= 0) return -1;
int low = 0, high = n-1;
while(low < high)
{
int mid = low+((high-low)>>1);
if(A[mid] < target)
low = mid+1;
else // A[mid] >= target
high = mid;
}
return low;
}
5—给定一个有序（非降序）数组A，可含有重复元素，求绝对值最小的元素的位置
这个问题也很简单，仅仅给出思路：
绝对值最小的数当然是0，这个问题转化为：找数组中0的位置，若没找到0,那么最终low==high指向的位置的数或者low-1（或者high-1）
指向的数就是最小的。
6—一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求target在变化后的数组中出现的位置，不存在则返回-1
如 0 1 2 4 5 6 7 可能变成 2 4 5 6 7 0 1
很明显的特征在于：有序数组旋转后，存在着两个有序部分。可能我们会想到对这两部分分别进行二分查找，这个思路总体上是没有问题的。但是问题在于我们如何知道这个数据转折点在哪？又或许我们是否有必要知道呢？
当然了，我们可以按照下面这个思路去处理问题：
第一步：寻找那个数据转折点（比如上述序列中就是7）
第二步，判断target所属区间（转折点前还是后）
第三步：二分查找
当然了，这个思路是完全ok的，也可以按照这个思路去处理，事实上，我开始也是这么做的。但是实际情况是，我们根本没有必要这么做，没必要去找那个数据转折点的位置。
因为这个数组旋转一次后，我们只需要关注旋转后的数组的中间元素，一个很重要的特点是：中间元素两边的子数组至少有一个是有序的。因此我们可以判断target是否在这个有序子数组中。从而决定target的搜索区间。
先上代码：
int searchInRotatedArray(int A[], int n, int target)
{
int low = 0, high = n-1;
while(low <= high)
{
int mid = low+((high-low)>>1);
if(A[mid] == target)
return mid;
if(A[mid] >= A[low])
{
// low ~ mid 是升序的
if(target >= A[low] && target < A[mid])
high = mid-1;
else
low = mid+1;
}
else
{
// mid ~ high 是升序的
if(target > A[mid] && target <= A[high])
low = mid+1;
else
high = mid-1;
}
}
return -1;
}
这段代码可以说是相当完美！
来分析一下：
整体而言，这段代码仍然采用二分查找法。也许我们会心有余悸，但是仔细分析发现，非常的巧妙。
if(A[mid] >= A[low])
这个判断是用来表明：前半段是否是是升序有序子序列。如果是的话：
if(target >= A[low] && target < A[mid])
high = mid-1;
如果同时要找的数大于首个数，而小于中间元素，那么要找的数就位于有序序列之间。自然也就执行了：
high = mid-1;
该算法的精华在于：
else
这个else是指不满足于上述if条件的所有可能。自然也包括了二分查找的另一半target > A[mid]。但是其作用不仅仅是这个。那他的作用是什么呢？
我们看，要想所查找target位于有序数组中，他需要满足：
A[mid] >= A[low] && target >= A[low] && target < A[mid]
或者:
A[mid] < A[low] && target > A[mid] && target <= A[high]
不满足上述条件的时候，发生了：
low = mid+1;
或者:
high = mid-1;
这样的意义何在呢？没错就是通过改变low和high的索引，改变了mid的位置，最终也就是随着迭代的进行，使得target总可以处于一个有序子数组中，并找到它。也就说，最重要的代码：就是那个
else
请再深入推敲上上述代码。尤其是else的作用。对这个问题进一步思考：如果这个数组存在重复元素，那么还能进行二分查找吗？显然不能，
加载全部内容