1 基本的二分查找
01-复杂度3 二分查找 (20分)
最开始使用的是递归，发现最后一个测试点超时了
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存线性表中最后一个元素的位置 */
};
List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );
int main()
{
List L;
ElementType X;
Position P;
L = ReadInput();
scanf("%d", &X);
P = BinarySearch( L, X );
printf("%d\n", P);
return 0;
}
/* 你的代码将被嵌在这里 */
Position search(ElementType Data[], Position l, Position r,ElementType X){
if (l==r){
return Data[l]==X? l:NotFound;
}
Position mid = (l+r)>>1;
if (Data[mid] == X){
return mid;
} else if (Data[mid] < X){
return search(Data, mid+1, r,X);
} else {
return search(Data, l, mid-1,X);
}
}
Position BinarySearch( List L, ElementType X ){
Position p = search(L->Data, 1, L->Last,X);
return p;
}
于是改成非递归的形式
Position BinarySearch( List L, ElementType X ){
Position p = 0;
Position l =1,r = L->Last;
while (l<=r){
Position mid = l +((r-l)>>1);
if (L->Data[mid] == X){
p = mid;
break;
}
else if (L->Data[mid] < X){
l = mid +1;
}
else {
r = mid -1;
}
}
if (p==0){
p = NotFound;
}
return p;
}
注意：
- 上面写的是简单的二分查找，要求数据顺序存储在数组中（如果是在链表中，查找的时候就不是O(1)复杂度了），而且没有重复数据
- 循环退出条件是
l<=r，不是l<r - 取mid可以写为
mid = l +((r-l)>>1);避免溢出，注意不要掉了两对括号，根据优先级（先算术运算，后移位运算，最后位运算），加法优先于右移。 - left 和 right 更新时不应该使用mid，而应该使用mid-1或者mid+1。因为当数组中没有指定元素时，我们的判断条件
while(l<=r)会导致程序陷入无限循环，相等才退出 - 数据量太小不适合二分查找，比如只有10个数据元素，循环就好了
- 数据量太大，比如1GB，由于二分查找需要连续的内存空间，所以也不适合
题外话：基于链表的二分查找其实是有的。Redis中的有序集合(sorted set)使用的“跳表（Skip List）”数据结构，就是一种基于链表的查找方法，查询效率O(logn)， 构建多级索引。
2 二分查找拓展
- 查找第一个值等于给定值的元素
- 查找最后一个值等于给定值的元素
- 查找第一个大于等于给定值的元素
- 查找最后一个小于等于给定值的元素
- 求一个数的算术平方根，精确到小数点后6位
- 木棒切割问题
1. 查找第一个值等于给定值的元素
如在数组{1,3,4,5,6,8,8,8,11,18}中希望查找第一个等于8的下标位置（下标从0开始），输入数据格式：
10
1 3 4 5 6 8 8 8 11 18
8
运行程序后得到的结果是5
public class Solution {
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
end = mid;
} else if (target < nums[mid]) {
end = mid;
} else {
start = mid;
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
}
#include <stdio.h>
int a[100];
int search(int a[], int size, int X){
int left = 0, right = size-1;
while(left<=right){
int mid = left + ((right - left) >> 1);
if (X > a[mid]){
left = mid + 1;
}
else if (X < a[mid]){
right = mid -1;
}
else{ // a[mid] == X
if (mid==0 || a[mid-1] < a[mid]){
return mid;
}
else {
right = mid - 1;
}
}
}
return -1;
}
int main(){
int n = 0,x=0;
scanf("%d", &n);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
}
scanf("%d", &x);
int pos = search(a,n,x);
printf("%d", pos);
}
2. 查找最后一个值等于给定值的元素
如在数组{1,3,4,5,6,8,8,8,11,18}中希望查找最后一个等于8的下标位置（下标从0开始），输入数据格式：
10
1 3 4 5 6 8 8 8 11 18
8
运行程序后得到的结果是7
public class Solution {
/**
* @param nums: An integer array sorted in ascending order
* @param target: An integer
* @return: An integer
*/
public int lastPosition(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
start = mid;
} else if (target < nums[mid]) {
end = mid;
} else {
start = mid;
}
}
if (nums[end] == target) {
return end;
}
if (nums[start] == target) {
return start;
}
return -1;
}
}
#include <stdio.h>
int a[100];
int search(int a[], int size, int X){
int left = 0, right = size-1;
while(left<=right){
int mid = left + ((right - left) >> 1);
if (X > a[mid]){
left = mid + 1;
}
else if (X < a[mid]){
right = mid -1;
}
else{ // a[mid] == X
if (mid==size-1 || a[mid+1] > a[mid]){
return mid;
}
else {
left = mid + 1;
}
}
}
return -1;
}
int main(){
int n = 0,x=0;
scanf("%d", &n);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
}
scanf("%d", &x);
int pos = search(a,n,x);
printf("%d", pos);
}
3. 查找第一个大于等于给定值的元素
如在数组{3,4,6,7,10}中希望查找第一个大于等于5的下标位置（下标从0开始），输入数据格式：
5
3 4 6 7 10
5
运行程序后得到的结果是2
#include <stdio.h>
int a[100];
int search(int a[], int size, int X){
int left = 0, right = size-1;
while(left<=right){
int mid = left + ((right - left) >> 1);
if (a[mid]>=X){
if (mid == 0 || a[mid-1] < X){
return mid;
}
else {
right = mid - 1;
}
}
else {
left = mid +1;
}
}
return -1;
}
int main(){
int n = 0,x=0;
scanf("%d", &n);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
}
scanf("%d", &x);
int pos = search(a,n,x);
printf("%d", pos);
}
4. 查找最后一个小于等于给定值的元素
如在数组{3,4,6,7,10}中希望查找最后一个小于等于5的下标位置（下标从0开始），输入数据格式：
5
3 4 6 7 10
5
运行程序后得到的结果是1
#include <stdio.h>
int a[100];
int search(int a[], int size, int X){
int left = 0, right = size-1;
while(left<=right){
int mid = left + ((right - left) >> 1);
if (a[mid] <= X){
if (mid == size-1 || a[mid+1] > X){
return mid;
}
else {
left = mid +1;
}
}
else {
right = mid - 1;
}
}
return -1;
}
int main(){
int n = 0,x=0;
scanf("%d", &n);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
}
scanf("%d", &x);
int pos = search(a,n,x);
printf("%d", pos);
}
5. 求一个数的算术平方根，精确到小数点后6位
#include <stdio.h>
const double eps=1e-7;
double f(double x){
return x*x;
}
double mysqrt(double n){
double left = 0;
double right = n;
double mid = -1;
while (right - left > eps){
mid = (left + right)/2;
if (f(mid) > n){
right = mid;
}
else {
left = mid;
}
}
return mid;
}
int main(){
int n = 0;
scanf("%d", &n);
double root = mysqrt(n);
printf("%lf", root);
}
6. 木棒切割问题
给出N个木棒，长度已知。现在希望通过切割它们得到至少K个长度相等的木棒（长长度是整数）。问这些长度相等的木棒最长有多长。
例如对于3根木棒，长度分别为10，24，15。想要得到至少7个长度相等的木棒，那么切割的木棒最长为6。
有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？
#include <stdio.h>
int a[10000];
int getCurrK(int len, int n){
int currK = 0;
for (int i=0;i<n;i++){
currK += a[i]/len;
}
return currK;
}
int main(){
int n=0,k=0,left=1,right=0,len = 0,sum=0;
scanf("%d %d", &n, &k);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
sum += a[i];
}
right = sum / k;
while (left <= right){
int mid = left + ((right - left)>>1);
int currK = getCurrK(mid, n);
if (currK < k){
right = mid - 1;
} else if (currK > k){
left = mid + 1;
} else {
if (mid == sum / k || getCurrK(mid+1, n)<k ){
len = mid;
break;
} else {
left = mid + 1;
}
}
}
printf("%d", len);
return 0;
}
3 最大子列和问题
最大子列和问题的三种解法
#include <stdio.h>
// O(n^3)
int maxSubSum(int a[], int size,int max){
for (int i=0;i<size;i++){
for (int j=i;j<size;j++){
int r = 0;
for (int k=i;k<=j;k++){
r+=a[k];
}
if (r > max){
max = r;
}
}
}
return max;
}
// O(n^2)
int maxSubSum2(int a[], int size,int max){
for (int i=0;i<size;i++){
int r = 0;
for (int j=i;j<size;j++){
r+=a[j];
if (r > max){
max = r;
}
}
}
return max;
}
int conquer(int a[], int left,int mid,int right,int lr,int rr){
int maxl = 0;
int r = 0;
for(int i=mid;i>=left;i--){
r+=a[i];
if (r>maxl){
maxl = r;
}
}
int maxr = 0;
r = 0;
for (int i=mid+1;i<=right;i++){
r+=a[i];
if (r>maxr){
maxr = r;
}
}
int maxlr = maxl + maxr;
if (maxlr >= lr && maxlr >= rr){
return maxlr;
} else if (lr > maxlr && lr > rr){
return lr;
} else if (rr > maxlr && rr > lr){
return rr;
}
}
// O(NLogN) 二分法
int maxSubSum3(int a[], int left,int right){
if (left == right){
return (a[left]>0)?a[left]:0;
}
else if (left < right){
int mid = (left + right) >> 1;
int lr = maxSubSum3(a,left,mid); // 获取左边最大
int rr = maxSubSum3(a,mid+1,right); // 获取右边最大
int max = conquer(a,left,mid,right,lr,rr); // 获取中间向两边扩展的最大值，并和左边、右边最大比较
return max;
}
}
int main(){
int a[8] = {4,-3,5,-2,-1,2,6,-2};
int max = 0;
max = maxSubSum3(a,0,7);
printf("%d", max);
return(0);
}
当然，最大子列和还有“在线处理”这种耗时O(N)的算法
01-复杂度2 Maximum Subsequence Sum (25分)
#include <stdio.h>
int a[100000];
int main(){
int n=0; // 读入n个数
int max=0, thisSum = 0; // max=最终结果，thisSum=当前和
scanf("%d", &n);
for (int i=0; i<n; i++){
scanf("%d", &a[i]);
thisSum += a[i];
if (thisSum < 0 ){ // 不可能使得后面的值增大了，抛弃
thisSum = 0;
}
if (thisSum >max){ // 更新当前结果
max = thisSum;
}
}
printf("%d", max);
return 0;
}
网友评论