二分函数出来了，可不知道怎么找最前的一个

P2249 【深基13.例1】查找

3_14 @ 2024-05-16 21:31:58

我的二分函数：

int search(int tar){
    int mi=0,ma=n-1;
    while(mi<=ma){
        int mid=(mi+ma)/2;
        if(a[mid]<tar)mi=mid+1; 
        else if(a[mid]>tar)ma=mid-1;
        else{
//          int cnt=a[mid];
//          if(mid-1>=0)
//              while(cnt==a[mid-1]&&mid>=0)
//                  mid--;
            return mid;
        }
    }
    return -1;
}

by weak_in_code @ 2024-05-16 21:36:06

@3_14 a_{mid}= tar 的时候不应该直接返回，应该缩 ma 找出现位置更小的。

by weak_in_code @ 2024-05-16 21:38:21

比如这么实现：

int mi=0,ma=n-1,ans=-1;
    while(mi<=ma){
        int mid=(mi+ma)/2;
        if(a[mid]<tar)mi=mid+1; 
        else if(a[mid]>=tar)ma=mid;

        if(a[mid]==tar) ans=mid;
    }
    return ans;

by Justin_love_coding @ 2024-05-16 21:45:32

@3_14 lower_bound()了解一下？

by 3_14 @ 2024-05-16 21:53:52

@Justin_love_coding 刚刚已经了解,谢谢

|