二分查找
二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過(guò)程從數(shù)組的中間元素開(kāi)始哟楷，如果中間元素正好是要查找的元素馍刮，則搜索過(guò)程結(jié)束簸搞；如果某一特定元素大于或者小于中間元素茉贡，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較者铜。如果在某一步驟數(shù)組 為空腔丧，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半作烟。折半搜索每次把搜索區(qū)域減少一半愉粤，時(shí)間復(fù)雜度為Ο(logn)。
二分查找的優(yōu)點(diǎn)是比較次數(shù)少拿撩，查找速度快衣厘，平均性能好；其缺點(diǎn)是要求待查表為有序表压恒，且插入刪除困難影暴。因此，二分查找探赫，是通過(guò)不斷縮小解可能存在的范圍型宙，從而求得問(wèn)題最優(yōu)解的方法，適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表伦吠。
二分查找算法要求
- 必須采用順序存儲(chǔ)結(jié)構(gòu)
- 必須按關(guān)鍵字大小有序排列
二分查找算法流程圖
二分查找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);
}
}
//二分查找的循環(huán)版本
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;
}
邊界錯(cuò)誤
二分查找算法的邊界一般分為兩種情況妆兑，一種為左閉右開(kāi)區(qū)間，如[low,high)毛仪，一種是左閉右閉區(qū)間搁嗓，如[low,high]。這里需要注意的是循環(huán)體外的初始化條件箱靴，與循環(huán)體內(nèi)的迭代步驟腺逛，都必須遵守一致的區(qū)間規(guī)則，也就是說(shuō)刨晴，如果循環(huán)體初始化時(shí)屉来，是以左閉右開(kāi)區(qū)間為邊界的路翻，那么循環(huán)體內(nèi)部的迭代也應(yīng)該如此。
Leetcode實(shí)例
Search in Rotated Sorted Array
要求
Suppose a sorted array is rotated at some pivot unknown to you beforehand
假設(shè)有一排好序的數(shù)組茄靠，它事先在某個(gè)軸心點(diǎn)處被旋轉(zhuǎn)
(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]區(qū)間的子數(shù)組為遞增序列慨绳，那它就可以用二分查找的方法去進(jìn)行查詢掉冶；否則，就會(huì)被繼續(xù)的劃分脐雪，知道子數(shù)組是一個(gè)遞增的數(shù)組為止厌小。反之也是同樣的道理。
由于last一直指向子數(shù)組最后一個(gè)元素的下一個(gè)位置战秋，所以在程序的賦值是要特別注意璧亚。
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.
作為上一題的變型，該題允許存在重復(fù)的元素
分析
允許重復(fù)元素脂信，則上一題中如果 A[middle]>=A[left], 那么 [left,middle] 為遞增序列的假設(shè)就不能成立了癣蟋，比如 [1,3,1,1,1]。
如果 A[m]>=A[l] 不能確定遞增狰闪，那就把它拆分成兩個(gè)條件：
- 若 A[m]>A[l]疯搅，則區(qū)間 [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;
}
};
二分查找思想的應(yīng)用
求最優(yōu)解問(wèn)題
二分查找的方法在求最優(yōu)解的問(wèn)題上也很有用。比如“求滿足某個(gè)條件C(x)的最小的x”這一問(wèn)題丽声。對(duì)于任意滿足C(x)的x如果所有x'>=x也滿足C(x')的話礁蔗，就可以用二分查找來(lái)求得最小的x。
首先我們將區(qū)間的左端點(diǎn)初始化為不滿足C(x)的值恒序，右端點(diǎn)初始化為滿足C(x)的值瘦麸。然后每次取中點(diǎn)mid=(lb+ub)/2,判斷C(mid)是否滿足并縮小范圍，直到(lb,ub]足夠小為止歧胁。最后ub就是要求的最小值滋饲。
同理，最大化的問(wèn)題也可以用同樣的方法求解喊巍。
假定一個(gè)解并判斷是否可行
有N條繩子屠缭，他們長(zhǎng)度分別為L(zhǎng)i。如果從它們中切割出K條長(zhǎng)度相同的繩子的話崭参，這K條繩子每條最長(zhǎng)能有多長(zhǎng)呵曹？答案保留到小數(shù)點(diǎn)后2位。
限制條件：
- 1<= N <= 10000
- 1<= K <= 10000
- 1<= Li <= 100000
分析
令條件為C(x)=可以得到K條長(zhǎng)度為x的繩子
則問(wèn)題變?yōu)榍鬂M足C(x)條件的最大的x。在區(qū)間初始化時(shí)奄喂，令下界為lb=0铐殃，上界為ub=INF。
轉(zhuǎn)化：
由于長(zhǎng)度為L(zhǎng)i 的繩子最多可以切出floor(Li/x)段長(zhǎng)度為x的繩子跨新，因此
C(x)=(floor(Li/x)的總和是否大于或者等于K)
代碼實(shí)例
#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;
}
二分查找的結(jié)束判定
在輸出小數(shù)的問(wèn)題中富腊，一般都會(huì)制定允許的誤差范圍或者制定輸出中小數(shù)點(diǎn)后面的位數(shù)。有必要設(shè)置合理的結(jié)束條件來(lái)滿足精度的要求域帐。
在上面的程序中赘被，我們制定循環(huán)次數(shù)作為終止條件。1次循環(huán)可以吧區(qū)間范圍縮小一半肖揣，100次循環(huán)則可以達(dá)到10的-30次冪的精度范圍民假，基本是沒(méi)有問(wèn)題的。
最大化平均值
有n個(gè)物品的重量和價(jià)值分別是wi和vi龙优。從中選出k個(gè)物品使得單位重量的價(jià)值最大羊异。
限制條件：
- 1<= k <= n <= 10^4
- 1<= wi,vi <= 10^6
分析
代碼實(shí)例
//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);
}
