欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关于二分查找的几个分类应用

程序员文章站 2022-06-02 12:12:30
...
#include<bits/stdc++.h>
using namespace std;
int e1(int a[],int n,int val)//二分查找val是否在数组里,不在返回-1
{
    int l=0,r=n-1;
    while(l<=r)
    {
        int mid=l+((r-l)>>1);
        if(a[mid]>val)
            r=mid-1;
        else if(a[mid]<val)
            l=mid+1;
        else
            return mid;
    }
    return -1;
}
int e2(int a[],int n,int val)//二分查找第一个等于val的值的下标
{
    int l=0,r=n-1;
    while(l<=r)
    {
        int mid=l+((r-l)>>1);
        if(a[mid]>=val)
            r=mid-1;
        else
            l=mid+1;
    }
    if(l<n&&a[l]==val)
        return l;
    return -1;
}
int e3(int a[],int n,int val)//二分查找最后一个等于val的值的下标
{
    int l=0,r=n-1;
    while(l<=r)
    {
        int mid=l+((r-l)>>1);
        if(a[mid]>val)
            r=mid-1;
        else
            l=mid+1;
    }
    if(r>=0&&a[r]==val)
        return r;
    return -1;
}
int e4(int a[],int n,int val)//二分查找第一个大于等于val的值的下标
{
    int l=0,r=n-1;
    while(l<=r)
    {
        int mid=l+((r-l)>>1);
        if(a[mid]>=val)
            r=mid-1;
        else
            l=mid+1;
    }
    return (l<n)?l:-1;
}
int e5(int a[],int n,int val)//二分查找最后一个小于等于val的值的下标
{
    int l=0,r=n-1;
    while(l<=r)
    {
        int mid=l+((r-l)>>1);
        if(a[mid]>val)
            r=mid-1;
        else
            l=mid+1;
    }
    return (r>=0)?r:-1;
}
int e6(int a[],int n,int val)//二分查找第一个小于val值的下标
{
    int l=0,r=n-1;
    while(l<=r)
    {
        int mid=l+((r-l)>>1);
        if(a[mid]>=val)
            r=mid-1;
        else
            l=mid+1;
    }
    return (r>=0)?r:-1;
}
int e7(int a[],int n,int val)//二分查找第一个大于val的值的下标
{
    int l=0,r=n-1;
    while(l<=r)
    {
        int mid=l+((r-l)>>1);
        if(a[mid]>val)
            r=mid-1;
        else
            l=mid+1;
    }
    return (l<n)?l:-1;
}
int main()
{
    int a[10]={1,2,2,4,5,5,5,8,9,10};
    printf("%d\n",e1(a,10,5));
    printf("%d\n",e2(a,10,5));
    printf("%d\n",e3(a,10,5));
    printf("%d\n",e4(a,10,5));
    printf("%d\n",e5(a,10,5));
    printf("%d\n",e6(a,10,5));
    printf("%d\n",e7(a,10,5));
    return 0;
}

输入为1,2,2,4,5,5,5,8,9,10

调用e1到e7七个二分查找函数会得出相应结果;

e1函数是查找是否存在val值并返回下标,不存在返回-1;

e2函数是查找第一个等于val的值并返回下标,不存在返回-1;

e3函数是查找最后一个等于val的值并返回下标,不存在返回-1;

e4函数是查找第一个大于等于val的值并返回下标,不存在返回-1;

e5函数是查找最后一个小于等于val的值并返回下标,不存在返回-1;

e6函数是查找第一个小于val值并返回下标,不存在返回-1;

e7函数是查找第一个大于val的值并返回下标,不存在返回-1;

关于二分查找的几个分类应用

相关标签: 二分查找