二分查找

二分查找又称折半查找，时间复杂度为O（log2n）。

二分查找的要求

1.给定一串数据，需要知道数据的上限和下限，而且必须用顺序存储结构。
2.要按照关键字进行排序。比如题目上给的数据可能是无序的，我们只要提前给数据进行处理使数据变成有序的就可以使用二分。至于排序有快速排序，冒泡，归并排序，堆排序…

二分查找的实现

给定一组有序数列，我们先给它规定边界即上限和下限，假设这个数的上限为right，这个数的下限是left。而我们每次取这组数的最中间的位置即mid=（right+left）/2 与要找的数进行比较，如果大于要找的数就把right=mid-1，这样它的查找范围就变为left----mid-1；如果小于要找的数就把left变为left=mid+1，查找范围就变为mid+1----right。然后再重复此过程直到mid等于他想的数就可以退出了。

二分查找模板

int find(int l,int r,int v)//l存储上界，r存储下界，v即为目标元素
{
    if(l>r) return -1;//如果找不到就返回-1
    int mid=(l+r)>>1;//mid即为中间元素的位置，这里用位运算提高效率，相当于"int mid=(l+r)/2;"
    //对中间元素与目标元素进行比较
    if(sum[mid]==v) return mid;//中间元素与目标元素相同，则退出函数，返回中间元素的位置
    else if(sum[mid]>v) find(l,mid-1);//中间元素大于目标元素，将上界更新为中间元素的位置-1
    else find(mid+1,r);//中间元素小于目标元素，将下界更新为中间元素的位置+1
}

还有一种非有序数组的二分查找的算法也算是了解学习一下具体看代码

int bSearch(int low, int high, int target)
{
	if (low > high)
	{
		if (num[low] == target)//这里需要判断low是否在数组范围内， 对于特殊数据会出现运行错误的
			return low + 1;
		else 
			return -1;
	}
	int mid = num[low];
	int left = low;
	int right = high;
	//这里能针对重复数数组
	while (left < right)
	{
		while (right > left && num[right] >= mid)
			--right;
		swap(num[left], num[right]);
		while (left < right && num[left] <= mid)
			++left;
		swap(num[left], num[right]);
	}
	if (mid < target)
		return bSearch(left + 1, high, target);
	else 
		return bSearch(low, left - 1, target);
}

hihocode#[1128 : 二分·二分查找(http://hihocoder.com/problemset/problem/1128)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000007;
int a[N],K,n;
int bSearch(int low, int high, int target)//无序二分查找 
{
	if (low > high)
	{
		if (a[low] == target)//这里需要判断low是否在数组范围内， 对于特殊数据会出现运行错误的
			return low + 1;
		else 
			return -1;
	}
	int mid = a[low];
	int left = low;
	int right = high;
	//这里能针对重复数数组
	while (left < right)
	{
		while (right > left && a[right] >= mid)
			--right;
		swap(a[left], a[right]);
		while (left < right && a[left] <= mid)
			++left;
		swap(a[left], a[right]);
	}
	if (mid < target)
		return bSearch(left + 1, high, target);
	else 
		return bSearch(low, left - 1, target);
}
int main(){
	scanf("%d%d",&n,&K);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	printf("%d\n", bSearch(0, n-1, K));
	return 0;
}