二分算法学习笔记

二分算法

	还是没写完！

---

参考文章:
二分算法总结
二分算法

---

二分查找

使用的前提条件：序列必须有序

典型的二分查找程序代码

BinarySearch

函数BinarySeach：在包含size个元素的、从小到大排序的int数组a里查找元素
p,如果找到，则返回元素下标，如果找不到，则返回-1。

int BinarySearch(int a[],int size,int p){
    int L = 0;//查找区间的左端点
    int R= size - 1;//查找区间的右端点
    while(L<R){//如果查找区间不为空就继续查找；
        int mid = L + (R-L)/2;//取查找区间正中元素的下标,这里的写法能防止溢出
        if (p==a[mid])
            return mid;
        else if(p > a[mid])
            L = mid + 1;//设置新的查找区间的左端点
        else
            R = mid - 1;//设置新的查找区间的右端点
    }
    return -1；
}//复杂度O(log(n))

LowerBound

函数LowerBound：在包含size个元素的、从小到大排序的int数组a里查找比给定整数p小的，下标最大的元素。找到则返回其下标，找不到则返回-1

int LowerBound(int a[], int size, int p){
    int L = 0;//查找区间的左端点
    int R = size -1;//查找区间的右端点
    int lastPos = -1;//到目前为止找到的最优解
    while(L <= R)//如果查找区间不为空就继续查找
    {
        int mid = L + (R-L)/2;//取查找区间正中元素的下标
        if(a[mid]>=p)
            R = mid -1;
        else{
            lastPos = mid;
            L = mid + 1;
        }
    }
    return lastPos;
}

相关题目

luogu P2249 【深基13.例1】查找

题目链接
难度:普及-

代码：

#include <bits/stdc++.h>
#define LEN 1000001
using namespace std;
long data[LEN]={0};
int main(){
    int n, m, q;
    cin >> n >> m;
    for (int i = 0; i < n;i++)
        cin >> data[i];
    while (m--)
    {
        cin >> q;
        int L = 0;
        int R = n - 1;
        int pos = -1;
        while(L<=R){
            int mid = L + (R-L)/2;
            if(data[mid]==q)
            {
                pos = mid+1;
                R = mid - 1;
            }
            else if(data[mid]>q)
                R = mid - 1;
            else
                L = mid + 1;
        }
        if(m==0)
            cout << pos << endl;
        else
            cout << pos << " ";
        
    }
    return 0;
}

luogu P1102 A-B 数对

题目链接
难度:普及-

代码：

#include <bits/stdc++.h>
#define LEN 200001
using namespace std;
int data[LEN] = {0};
int main(){
    int n, c;
    while(cin>>n>>c){
        for (int i = 0; i < n;i++)
            cin >> data[i];
        long sum = 0;
        sort(data, data + n);
        for (int i = n - 1; i > 0&&data[i]-c>=1;i--)
        {
            int L = 0;
            int R = i;
            int pos1=-1,pos2=-1;
            int q = data[i] - c;
            while(L<=R){
                int mid = L + (R - L) / 2;
                if (data[mid]==q)
                {
                    pos1 = mid;
                    R = mid - 1;
                }
                else if(data[mid]>q)
                    R = mid - 1;
                else
                    L = mid + 1;
            }
            L = 0;
            R = i;
            while(L<=R){
                int mid = L + (R - L) / 2;
                if (data[mid]==q)
                {
                    pos2 = mid;
                    L = mid + 1;
                }
                else if(data[mid]>q)
                    R = mid - 1;
                else
                    L = mid + 1;
            }
            if(pos1!=-1)
                sum += pos2 - pos1 + 1;
        }
        cout << sum << endl;
    }
    return 0;
}