简单的二分查找

  二分查找的前提是序列有序，其高效之处在于每一步都可以去除当前区间中一半的元素，时间复杂度为O(logn)；刷题中若遇到有序序列的查找，第一联想到这个简单的算法。

Code

int binarySearch(vector<int> arr,int begin,int end,int target){
	int mid;
	while(begin<=end){
		mid = (begin+end)/2;
		if(arr[mid]==target)
			return mid;
		if(arr[mid]>target)
			end = mid-1;
		if(arr[mid]<target)
			begin = mid+1;
	}
	return -1;
}