很多其它请关注我的HEXO博客:http://jasonding1354.github.io/
简书主页:http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles
二分查找
二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素開始,假设中间元素正好是要查找的元素,则搜索过程结束;假设某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,并且跟開始一样从中间元素開始比較。假设在某一步骤数组 为空,则代表找不到。这样的搜索算法每一次比較都使搜索范围缩小一半。折半搜索每次把搜索区域降低一半,时间复杂度为Ο(logn)。
二分查找的长处是比較次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,二分查找,是通过不断缩小解可能存在的范围,从而求得问题最优解的方法,适用于不常常变动而查找频繁的有序列表。
二分查找算法要求
- 必须採用顺序存储结构
- 必须按keyword大小有序排列
二分查找算法流程图
二分查找c源代码
//二分查找的递归版本号
int binary_search_recursion(const int array[], int low, int high, int key)
{
int mid = low + (high - low)/2;
if(low > high)
return -1;
else{
if(array[mid] == key)
return mid;
else if(array[mid] > key)
return binary_search_recursion(array, low, mid-1, key);
else
return binary_search_recursion(array, mid+1, high, key);
}
}
//二分查找的循环版本号
int binary_search_loop(const int array[], int len, int key)
{
int low = 0;
int high = len - 1;
int mid;
while(low <= high){
mid = (low+high) / 2;
if(array[mid] == key)
return mid;
else if(array[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
边界错误
二分查找算法的边界一般分为两种情况,一种为左闭右开区间,如[low,high),一种是左闭右闭区间,如[low,high]。这里须要注意的是循环体外的初始化条件,与循环体内的迭代步骤,都必须遵守一致的区间规则,也就是说,假设循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此。
Leetcode实例
Search in Rotated Sorted Array
要求
Suppose a sorted array is rotated at some pivot unknown to you beforehand
如果有一排好序的数组,它事先在某个轴心点处被旋转
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2 )
You are given a target value to search.
If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
分析
二分查找,难度在于左右边界的确定
假设A[middle] <= A[first],则[middle,last-1]区间的子数组为递增序列,那它就能够用二分查找的方法去进行查询;否则,就会被继续的划分,知道子数组是一个递增的数组为止。反之也是相同的道理。
因为last一直指向子数组最后一个元素的下一个位置,所以在程序的赋值是要特别注意。
C++代码
class Solution {
public:
int search(int A[], int n, int target) {
int first = 0;
int last = n;
while(first != last)
{
int middle = (first + last)/2;
if(A[middle] == target)
return middle;
if(A[first] >= A[middle]){
if(target > A[middle] && target <= A[last-1])
first = middle+1;
else
last = middle;
}
else
{
if(target < A[middle] && target >= A[first])
last = middle;
else
first = middle+1;
}
}
return -1;
}
};
Search in Rotated Sorted Array II
要求
Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed?
Write a function to determine if a given target is in the array.
作为上一题的变型,该题同意存在反复的元素
分析
同意反复元素,则上一题中如果 A[middle]>=A[left], 那么 [left,middle] 为递增序列的如果就不能成立了,比方 [1,3,1,1,1]。
假设 A[m]>=A[l] 不能确定递增,那就把它拆分成两个条件:
- 若 A[m]>A[l],则区间 [l,m] 一定递增
- 若 A[m]==A[l] 确定不了,那就 l++,往下看一步就可以。
c++代码
class Solution {
public:
bool search(int A[], int n, int target) {
int first = 0,last = n;
while(first != last)
{
int mid = (first+last)/2;
if(A[mid] == target)
return true;
if(A[mid] == A[first])
first++;
else if(A[mid] > A[first])
{
if(A[first]<= target && A[mid] > target)
last = mid;
else
first = mid+1;
}
else
{
if(A[mid] < target && A[last-1] >= target)
first = mid+1;
else
last = mid;
}
}
return false;
}
};
二分查找思想的应用
求最优解问题
二分查找的方法在求最优解的问题上也非常实用。比方“求满足某个条件C(x)的最小的x”这一问题。对于随意满足C(x)的x假设全部x'>=x也满足C(x')的话,就能够用二分查找来求得最小的x。
首先我们将区间的左端点初始化为不满足C(x)的值,右端点初始化为满足C(x)的值。然后每次取中点mid=(lb+ub)/2,推断C(mid)是否满足并缩小范围,直到(lb,ub]足够小为止。最后ub就是要求的最小值。
同理,最大化的问题也能够用相同的方法求解。
假定一个解并推断是否可行
有N条绳子,他们长度分别为Li。假设从它们中分割出K条长度同样的绳子的话,这K条绳子每条最长能有多长?答案保留到小数点后2位。
限制条件:
- 1<= N <= 10000
- 1<= K <= 10000
- 1<= Li <= 100000
分析
令条件为C(x)=能够得到K条长度为x的绳子
则问题变为求满足C(x)条件的最大的x。在区间初始化时,令下界为lb=0,上界为ub=INF。
转化:
因为长度为Li 的绳子最多能够切出floor(Li/x)段长度为x的绳子,因此
C(x)=(floor(Li/x)的总和是否大于或者等于K)
代码实例
#include <iostream>
#include <math.h>
using namespace std;
#define MAX_N 10
int N = 4;
int K = 10;
double L[MAX_N] = {8.02,7.43,4.57,5.39};
bool C(double x)
{
int num = 0;
for(int i=0;i<N;i++)
{
num += (int)(L[i]/x);
}
return num >= K;
}
void solve()
{
double lb = 0;
double ub = 1000;
for(int i=0;i<100;i++)
{
double mid = (lb+ub)/2;
if(C(mid)) lb = mid;
else ub = mid;
}
cout << floor(ub*100)/100<<endl;
}
int main() {
solve();
return 0;
}
二分查找的结束判定
在输出小数的问题中,一般都会制定同意的误差范围或者制定输出中小数点后面的位数。有必要设置合理的结束条件来满足精度的要求。
在上面的程序中,我们制定循环次数作为终止条件。1次循环能够吧区间范围缩小一半,100次循环则能够达到10的-30次幂的精度范围,基本是没有问题的。
最大化平均值
有n个物品的重量和价值各自是wi和vi。从中选出k个物品使得单位重量的价值最大。
限制条件:
- 1<= k <= n <= 10^4
- 1<= wi,vi <= 10^6
分析
代码实例
//input
int n,k;
int w[MAX_N],v[MAX_N];
double y[MAX_N];// v - x * w
bool C(double x)
{
for(int i=0;i<n;i++){
y[i] = v[i] - x*w[i];
}
sort(y,y+n);
//compute the sum of top-k number(array y)
double sum = 0;
for(int i=0;i<k;i++){
sum+=y[n-i-1];
}
return sum >= 0;
}
void solve()
{
double lb=0,ub=INF;
for(int i=0;i<100;i++){
double mid = (lb+ub)/2;
if(C(mid))
lb = mid;
else
ub = mid;
}
printf("%.2f\n",ub);
}