二分查找

普通二分

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n,a[50010],l,r,mid,ans,x;  //n是数列长度，a数组是数列，l是起点，r是终点，mid是数列中点，ans是最终答案，x是询问的值 
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)cin>>a[i];
    l=1,r=n;
    while(l<=r)
    {
        mid=(l+r)/2;    //取数列中点
        if(a[mid]<x)l=mid+1;   //如果比x小的话，就证明1~mid都比x小，去mid+1~r找(数组有序，从小到大) 
        else if(a[mid]>x)r=mid-1;    //如果比x大的话，就证明mid~r都比x大，去l~mid-1找
        else    //证明找到了 
        {
            ans=mid;
            break;
        }
    }
    cout<<ans;
    return 0;
}

左边二分

#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int arr[N];
int n;

int leftBinarySearch(int left,int right,int target) {


    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1; // 目标值在右侧
        }
        else {
            right = mid; // 目标值在左侧或当前位置
        }
    }
    return left; // 返回第一个大于等于目标值的位置
}

int main() {
    cout << "输入数组长度：";
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }   
    int target;
    cout << "输入需要查找的目标值:";
    cin >> target;

    int result = leftBinarySearch(0,n, target);

    cout << "第一个大于等于目标值 " << target << " 的位置为: " << result << endl;

    return 0;
}

右边二分

#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int arr[N];
int n;

int leftBinarySearch(int left, int right, int target) {
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid ; // 目标值在右侧
        }
        else {
            right = mid-1; // 目标值在左侧或当前位置
        }
    }
    return left; // 返回第一个大于等于目标值的位置
}

int main() {
    cout << "输入数组长度：";
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int target;
    cout << "输入需要查找的目标值:";
    cin >> target;

    int result = leftBinarySearch(0, n, target);

    cout << "第一个大于等于目标值 " << target << " 的位置为: " << result << endl;

    return 0;
}

进阶算法

评论