文章目录
二分思想二分应用二分查找求第一个大于等于x的元素位置求第一个大于x的元素的位置求最后一个小于x的元素的位置求最后一个小于等于x的元素的位置快速幂
二分思想
假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，
如果当前位置arr[k]值等于key，则查找成功；若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]， 直到找到为止,时间复杂度:O(log(n))
当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。
二分应用
二分查找
求第一个大于等于x的元素位置
求第一个大于x的元素的位置
求最后一个小于x的元素的位置
第一个大于等于x的元素位置-1
求最后一个小于等于x的元素的位置
第一个大于x的元素的位置-1
快速幂
#include <iostream>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std
;
int binarySearch(int arr
[],int l
,int r
, int x
) {
if(l
>r
)return -1;
int mid
= l
+((r
-l
)>>1);
if(arr
[mid
]==x
)return mid
;
else if(arr
[mid
]>x
) {
binarySearch(arr
,l
,mid
-1,x
);
} else {
binarySearch(arr
,mid
+1,r
,x
);
}
}
int binarySearch(int arr
[],int len
,int x
) {
return binarySearch(arr
, 0, len
-1, x
);
}
int lower_bound(int arr
[],int l
,int r
, int x
) {
int mid
;
while(l
<r
) {
mid
=l
+((r
-l
)>>1);
if(arr
[mid
]>=x
) {
r
= mid
;
} else {
l
= mid
+1;
}
}
return l
;
}
int lower_bound(int arr
[],int len
,int x
) {
return lower_bound(arr
, 0, len
-1, x
);
}
int upper_bound(int arr
[],int l
,int r
, int x
) {
int mid
;
while(l
<r
) {
mid
=l
+((r
-l
)>>1);
if(arr
[mid
]>x
) {
r
= mid
;
} else {
l
= mid
+1;
}
}
return l
;
}
int upper_bound(int arr
[],int len
,int x
) {
return upper_bound(arr
, 0, len
-1, x
);
}
long long binaryPow(int a
,int b
) {
if(b
==0)return 1;
if(b
%2==1)
return a
*binaryPow(a
, b
-1);
else {
long long bp
= binaryPow(a
,b
>>1);
return bp
*bp
;
}
}
int main(int argc
,char * argv
[]) {
int A
[10]= {1,2,2,3,4,5,5,5,8,9};
printf("----------- binary search ----------\n");
printf("%d\n",binarySearch(A
,10,1));
printf("%d\n",binarySearch(A
,10,9));
printf("%d\n",binarySearch(A
,10,10));
printf("----------- lower bound ----------\n");
printf("%d\n",lower_bound(A
,10,2));
printf("%d\n",lower_bound(A
,10,5));
printf("%d\n",lower_bound(A
,10,8));
printf("----------- upper bound ----------\n");
printf("%d\n",upper_bound(A
,10,2));
printf("%d\n",upper_bound(A
,10,5));
printf("%d\n",upper_bound(A
,10,8));
printf("%d\n",upper_bound(A
,10,10));
return 0;
}
