【算法系列】二分法算法

二分法

  • 对于区间[a,b]上连续不断且f ( a ) ⋅ f ( b ) < 0 f(a)·f(b)<0f(a)⋅f(b)<0的函数y = f ( x ) y=f(x)y=f(x),通过不断地把函数f ( x ) f(x)f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法叫二分法。
  • 通俗语言就是将搜索空间不断的减半,从而逼近解的过程

从二分查找来看二分法

例子:在一个一维有序数组中,判断数组中是否有值为target的数存在。

  • 首先判断数组中间值是否大于目标值,如果大于,则将搜索空间变为前半段,删除后半段。反之同理

迭代算法(时间复杂度O(log(n)),空间复杂度O(1))

int binarySearch(vector<int> arr,int key){ 
	int low=0;//数组最小的索引值
	int high=arr.size()-1;//数组最大索引值
	while(low<high){ 
		int mid == (low+high)/2;
		if(key == arr[mid]){ 
			return mid+1;
		}else if(key > arr[mid]){ 
			low = mid+1;
		}else{ 
			high = mid-1;
		}
	}
	return -1;//没有找到
}

递归算法(时间复杂度O(log(n)),空间复杂度O(n))

int binarySearch(vector<int> arr,int low,int high,int key){ 
	if(low > high){ 
		return -1;
	}
	int mid = (low+high)/2;
	if(key == arr[mid]){ 
		return mid+1;
	}else if(key < arr[mid]){ 
		high = mid-1;
		return binarySearch(arr,low,high,key);
	}else{ 
		low=mid+1;
		return binarySearch(arr,low,high,key);
	}
}
    原文作者:然木酥
    原文地址: https://blog.csdn.net/xinxin_____/article/details/109134011
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞