二分查找法是一种基础的算法,应用于在有序元素序列中查找目标值。二分查找法思路清晰,可以描述为以下几个步骤:
二分查找法
二分查找法的代码及其简单:
int binarySearch(int arr[], int n, int target){
assert(n >= 0);
int l = 0, r = n - 1;
while (l < r){
int mid = l + (r - l) / 2;
if (arr[mid] < target){
l = mid + 1;
}
else if (arr[mid]>target){
r = mid - 1;
}
else{
return mid;
}
}
return -1;
}
其中,对mid的计算改为了mid = l + (r - l) / 2,主要是避免溢出。
问题
对于下面这样一个有序序列,用上面的代码分别查找12、50和95:
测试代码如下:
int main()
{
int arr[10] = { 0,12,38,49,50,50,68,79,95,100};
printf("Position:");
for (int i = 0; i < 10; i++){
printf("%4d", i);
}
printf("\n ");
for (int i = 0; i < 10; i++){
printf(" | ");
}
printf("\nValue :");
for (int i = 0; i < 10; i++){
printf("%4d", arr[i]);
}
printf("\n\n");
printf("BinarySearch\n");
printf("binarySearch(12), Position is %d\n", binarySearch(arr, 10, 12));
printf("binarySearch(50), Position is %d\n", binarySearch(arr, 10, 50));
printf("binarySearch(95), Position is %d\n", binarySearch(arr, 10, 95));
system("pause");
return 0;
}
运行结果如下图:
12和95都可以准确找到位置,因为序列中他们都只出现过一次。50的位置其实也是准确的,只不过序列中有两个50,上述算法找出来的是第1个位置的50。这是因为第一次计算出来的mid位置4就正好是50,所以直接返回了4。所以,可以理解如果是下面这样一个有序序列,使用上述代码查找50的位置,也会返回4.
有时候这样可能并不是我们想要的结果。我们可能想查找序列中第一次出现目标值,或者最后一次出现目标值,甚至是查找一个有序序列中第一个不小于目标值的元素出现的位置,或者查找第一个不大于目标值的元素出现的位置。
Ceil和Floor
为了解决上述两个问题,同样可以使用二分查找的思想设计ceil和floor函数。ceil意为天花板,即向上查找;floor意为地板,即向下查找。代码如下:
int ceil(int arr[], int n, int target){
int l = 0, r = n;
while (l < r){
int mid = l + (r - l) / 2;
if (arr[mid] <= target){
l = mid + 1;
}
else{
r = mid;
}
}
assert(l == r);
if (l - 1 >= 0 && arr[l - 1] == target){
return l - 1;
}
return l;
}
int floor(int arr[], int n, int target){
assert(n >= 0);
int l = -1, r = n - 1;
while (l < r){
int mid = l + (r - l + 1) / 2;
if (arr[mid] >= target){
r = mid - 1;
}
else{
l = mid;
}
}
assert(l == r);
if (l + 1 < n && arr[l + 1] == target){
return l + 1;
}
return l;
}
接下来对上述两个函数做个测试:
int main()
{
int arr[10] = {0,12,50,50,50,50,50,50,95,100};
printf("Position:");
for (int i = 0; i < 10; i++){
printf("%4d", i);
}
printf("\n ");
for (int i = 0; i < 10; i++){
printf(" | ");
}
printf("\nValue :");
for (int i = 0; i < 10; i++){
printf("%4d", arr[i]);
}
printf("\n\n");
printf("\nCeil\n");
printf("ceil(12), Position is %d\n", ceil(arr, 12, 12));
printf("ceil(50), Position is %d\n", ceil(arr, 12, 50));
printf("ceil(80), Position is %d\n", ceil(arr, 12, 80));
printf("\nFloor\n");
printf("floor(12), Position is %d\n", floor(arr, 12, 12));
printf("floor(50), Position is %d\n", floor(arr, 12, 50));
printf("floor(80), Position is %d\n", floor(arr, 12, 80));
printf("\n");
system("pause");
return 0;
}
该测试中,我们使用ceil和floor函数分别对给定的有序序列中的12、50和80进行查找。其中,
测试结果如下:
对于目标值50,ceil函数查找的结果为7,floor函数的查找结果为2。对于序列中不存在的元素80,ceil函数查找的结果为8,即95;而floor函数的结果为7。测试结果符合预期。
二分查找相关题目
LeetCode上关于二分查找的题目不少,比如:
比如第540题:
这道题直接用位运算中的异或运算,将特别痛快:
int singleNonDuplicate(vector<int>& nums) {
int ret = 0;
for (int i = 0; i<nums.size(); i++){
ret ^= nums[i];
}
return ret;
}
但是题目要求时间复杂度为O(logn),上述代码的时间复杂度为O(n),不符合题目要求。时间复杂度为O(logn),多半就是二分了。一番分析后,代码如下:
int singleNonDuplicate(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
while (l<r){
int mid = l + (r - l) / 2;
if (mid % 2 == 0){
if (nums[mid] == nums[mid + 1]){
l = mid + 2;
}
else if (nums[mid] == nums[mid - 1]){
r = mid - 2;
}
else{
return nums[mid];
}
}
else{
if (nums[mid] == nums[mid + 1]){
r = mid - 1;
}
else if (nums[mid] == nums[mid - 1]){
l = mid + 1;
}
else{
return nums[mid];
}
}
}
return nums[l];
}
二分查找法O(logn)的时间复杂度让它成为十分高效的算法。不过别忘了使用二分查找法的前提,即元素有序+数组。