PTA刷題總結(jié)-Part3.2 二分法專題

1 基本的二分查找

01-復(fù)雜度3 二分查找 (20分)
最開始使用的是遞歸，發(fā)現(xiàn)最后一個測試點超時了

#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(); /* 裁判實現(xiàn)，細(xì)節(jié)不表。元素從下標(biāo)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;
}

注意：

  • 上面寫的是簡單的二分查找，要求數(shù)據(jù)順序存儲在數(shù)組中（如果是在鏈表中，查找的時候就不是O(1)復(fù)雜度了），而且沒有重復(fù)數(shù)據(jù)
  • 循環(huán)退出條件是l<=r，不是l<r
  • 取mid可以寫為mid = l +((r-l)>>1);避免溢出，注意不要掉了兩對括號，根據(jù)優(yōu)先級（先算術(shù)運算，后移位運算，最后位運算），加法優(yōu)先于右移。
  • left 和 right 更新時不應(yīng)該使用mid，而應(yīng)該使用mid-1或者mid+1。因為當(dāng)數(shù)組中沒有指定元素時，我們的判斷條件while(l<=r)會導(dǎo)致程序陷入無限循環(huán)，相等才退出
  • 數(shù)據(jù)量太小不適合二分查找，比如只有10個數(shù)據(jù)元素，循環(huán)就好了
  • 數(shù)據(jù)量太大，比如1GB，由于二分查找需要連續(xù)的內(nèi)存空間，所以也不適合

題外話：基于鏈表的二分查找其實是有的。Redis中的有序集合(sorted set)使用的“跳表（Skip List）”數(shù)據(jù)結(jié)構(gòu)，就是一種基于鏈表的查找方法，查詢效率O(logn)， 構(gòu)建多級索引。

2 二分查找拓展

  1. 查找第一個值等于給定值的元素
  2. 查找最后一個值等于給定值的元素
  3. 查找第一個大于等于給定值的元素
  4. 查找最后一個小于等于給定值的元素
  5. 求一個數(shù)的算術(shù)平方根，精確到小數(shù)點后6位
  6. 木棒切割問題

1. 查找第一個值等于給定值的元素
如在數(shù)組{1,3,4,5,6,8,8,8,11,18}中希望查找第一個等于8的下標(biāo)位置（下標(biāo)從0開始），輸入數(shù)據(jù)格式：

10
1 3 4 5 6 8 8 8 11 18
8

運行程序后得到的結(jié)果是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. 查找最后一個值等于給定值的元素
如在數(shù)組{1,3,4,5,6,8,8,8,11,18}中希望查找最后一個等于8的下標(biāo)位置（下標(biāo)從0開始），輸入數(shù)據(jù)格式：

10
1 3 4 5 6 8 8 8 11 18
8

運行程序后得到的結(jié)果是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. 查找第一個大于等于給定值的元素
如在數(shù)組{3,4,6,7,10}中希望查找第一個大于等于5的下標(biāo)位置（下標(biāo)從0開始），輸入數(shù)據(jù)格式：

5
3 4 6 7 10
5

運行程序后得到的結(jié)果是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. 查找最后一個小于等于給定值的元素
如在數(shù)組{3,4,6,7,10}中希望查找最后一個小于等于5的下標(biāo)位置（下標(biāo)從0開始），輸入數(shù)據(jù)格式：

5
3 4 6 7 10
5

運行程序后得到的結(jié)果是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. 求一個數(shù)的算術(shù)平方根，精確到小數(shù)點后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個木棒，長度已知?，F(xiàn)在希望通過切割它們得到至少K個長度相等的木棒（長長度是整數(shù)）。問這些長度相等的木棒最長有多長。
例如對于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);
}

當(dāng)然，最大子列和還有“在線處理”這種耗時O(N)的算法
01-復(fù)雜度2 Maximum Subsequence Sum (25分)

#include <stdio.h>
int a[100000];
int main(){
    int n=0; // 讀入n個數(shù)
    int max=0, thisSum = 0; // max=最終結(jié)果，thisSum=當(dāng)前和
    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){ // 更新當(dāng)前結(jié)果
            max = thisSum;
        }
    }
    printf("%d", max);
    return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容