关于二分查找的几个分类应用
程序员文章站
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;
上一篇: 方法2:二分查找法