C/C++分治算法(1)——二分查找_c++ 二分查找

常见分治算法总结（1）二分查找

一篇文章，带你搞懂 二分查找 (注：代码语言的选择不应该限制了我们对算法的理解)

文章附有动图！一看就懂！

温馨提示：代码在文章末尾

---

二分查找又叫折半查找，顾名思义，指的是每次的查找范围折半。

优点：比较次数少、查找速度快、平均性能好。

缺点：要求待查找的数据已被整理为有序，换而言之，就是要求数组有序

主要功能：在一个已按非降序排序的序列Array中，查找是否存在一个元素key，如果存在，返回该元素的索引值，否则返回-1（c语言中数组的任何元素索引都不可能为-1，利用这点，使用-1表示不存在该元素）

 
实现原理：
1、确定有序序列的中位数Array[mid],并且将该中位数与key相比较。
2、如果Array[mid]>key,说明key可能在序列前半部分；否则Array[mid]<key，说明，key可能在序列后半部分；这种情况直接排除序列另外一部分（序列的一半）。如果碰巧Array[mid]=key；这时即可直接确定key索引值。

查找成功的情况

假设原始序列为array=[3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82]，目标元素target=52。

1. 开始时，low=0，high=10，mid=(low + high) / 2 = 5。

比较中间元素和目标元素，48小于52。这说明若目标元素存在，则它必定在原序列的后半部分。让low=mid + 1 = 6而high不变，这样low和high就指向了原序列的后半部分。

2. 此时，low=6，high=10，mid=(low + high) / 2 = 8。

同样的，比较新的中间元素和目标元素，69大于52。这说明若目标元素存在，它必定在当前待查序列的前半部分。让high=mid - 1 = 7而low不变，这样low和high就指向当前待查序列的前半部分。

3. 此时，low=6，high=7，mid=(low + high) / 2 = 6。

比较新的中间元素和目标元素，52等于52。查找成功，返回该中间元素的索引6并退出算法。

 

查找不到的情况

假设原始序列为array=[5, 10, 22, 29, 43, 57, 58, 61, 73, 77, 81]，目标元素target=70。

1. 开始时，low=0，high=10，mid=(low + high) / 2 = 5；

 比较中间元素和目标元素，57小于70。这说明若目标元素存在，那么它一定在原序列的后半部分。让low=mid + 1 = 6而high不变，这样low和high就指向原序列的后半部分。

2. 此时，low=6，high=10，mid=(low + high) / 2 = 8；

比较新的中间元素和目标元素，73大于70。这说明若目标元素存在，那么它一定在当前待查序列的前半部分。让high=mid - 1 = 7而low不变，这样low和high就指向当前待查序列的前半部分。

3. 此时，low=6，high=7，mid=(low + high) / 2 = 6；

比较新的中间元素和目标元素，58小于70。这说明若目标元素存在，那么它一定在当前待查序列的后半部分。让low=mid + 1 = 7而high不变，这样low和high就指向当前待查序列的后半部分。

4. 此时，low=7，high=7，mid=(low + high) / 2 = 7；

比较新的中间元素和目标元素，61小于70。这说明若目标元素存在，那么它一定在当前待查序列的后半部分。让low=mid + 1 = 8而high不变。

 5. 此时，low=8，high=7，low大于high说明待查序列已为空，也就说明查找不到目标元素。此时，返回-1并退出算法，表示查找不成功；

我们通过动态图来对比一下二分查找和顺序查找的性能，明显看出二分查找速度之快

非递归代码实现

#include<iostream>
using namespace std;
int binarySearch(int arr[],int n,int value){
	int low = 0;
	int high = n-1;
	//这里我们默认从小到大排序
	while(low <= high){
		int mid = low + ((high - low) /2);//也可以是mid=(low+high)/2
		if(arr[mid]==value) return mid;
		else if(arr[mid] > value){
			//中间比value大，往左边（较小）的方向找
			high = mid - 1;
		}else if(arr[mid] < value){
			//中间比value小，往右边（较大）的方向找
			low = mid + 1;
		}
	}
	return -1;
}
int main(){
	int i,value=26;
	int arr[10]={1,5,7,13,17,23,26,36,48,88};
	printf("原始数组:\n");
	for(i=0;i<10;i++) printf("%d ",arr[i]);
	printf("\n待查找的数据:%d\n",value);
	int ans = binarySearch(arr,10,value);
	if(ans!=-1){
		printf("%d在数组的下标为：%d\n",value,ans);
	}else{
		printf("没有找到%d\n",value);
	}
	return 0;
}

递归代码实现

#include<iostream>
using namespace std;
int binarySearch(int arr[],int low,int high,int value){
	//这里我们默认从小到大排序
	if(low > high) return -1;
	//找中间下标
	int mid = low + ((high - low) /2);//也可以是mid=(low+high)/2
	
	if(arr[mid]==value) return mid;
	else if(arr[mid] > value){
		//中间比value大，往左边（较小）的方向找
		binarySearch(arr,low,mid-1,value);
	}else if(arr[mid] < value){
		//中间比value小，往右边（较大）的方向找
		binarySearch(arr,mid+1,high,value);
	}
	
}
int main(){
	int i,value=26;
	int arr[10]={1,5,7,13,17,23,26,36,48,88};
	printf("原始数组:\n");
	for(i=0;i<10;i++) printf("%d ",arr[i]);
	printf("\n待查找的数据:%d\n",value);
	int ans = binarySearch(arr,0,10-1,value);
	if(ans!=-1){
		printf("%d在数组的下标为：%d\n",value,ans);
	}else{
		printf("没有找到%d\n",value);
	}
	return 0;
}