二分查找

• 对于有序数列才能使用二分查找

实现

递归实现

private int search(int[] data,int target){
    search(data,0,data.length-1,target);
}

private int search(int[] data,int l,int r,int target){
    if(l>r){
        return -1;
    }
    int mid = l+(r-l)/2;
    if(data[mid]==target){
        return mid;
    }
    if(data[mid]<target){
        return search(data,mid+1,r,target);
    }
    return search(data,l,mid-1,target);
}

非递归实现

private int seach(int[] data,int target){
    int l =0;
    int r = data.length-1;
    while(l<=r){
        int mid = l+(r-l)/2;
        if(data[mid] == target){
            return mid;
        }
        if(data[mid]<target){
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    return -1;
}

二分查找变种

• 大于target的最小值索引

private int upper(int[] data,int target){
    int l = 0;
    int r = data.length;
    while(l<r){
       int mid = l+(r-l)/2;
       if(data[mid]<=target){
        l = mid+1;
       }else{
        r=mid;
       }
    }
    return l;
}

• 如果存在target则返回最大索引,不存在则返回upper

private int ceil(int[] data,int target){
    int u = upper(data,target);
    return (u-1>=0&&data[u-1]==0)?u-1:u;
}

• 小于target的最大索引值

private int lower(int[] data,int target){
    int l =-1;
    int target = data.length-1;
    while(l<r){
        int mid = l+(r-l+1)/2;
        if(data[mid]<target){
            l=mid;
        }else{
            r = mid-1;
        }
    }
    return l;
}

应用

• 爱吃香蕉的珂珂(875)

private int minEatingSpeed(int[] piles,int H){
    int l = 1;
    int r = Arrays.stream(piles).max().getAsInt();
    while(l<r){
        int mid = l+(r-l)/2;
        if(eatingTime(piles,mid)<=H){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    return l;
}

private int eatingTime(int[] piles,int k){
    int res = 0;
    for(int pile:piles){
        res+=pile/k+(pile%k>0?1:0);
    }
    return res;
}

• 在D天内送达包裹的能力(1011)

private int shipWithinDays(int[] weights,int D){
    int l = Arrays.stream(weights).max().getAsInt();
    int r = Arrays.stream(weights).sum();
    while(l<r){
        int mid = l+(r-l)/2;
        if(days(weights,mid)<=D){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    return l;
}

private int days(int[] weights,int k){
    int cur=0;
    int res=0;
    for(int weight:weights){
        if(cur+weight<=k){
            cur+=weight;
        }else{
            res++;
            cur=weight;
        }
    }
    res++;
    return res;
}