偏移数组的二分查找

10
5 6 7 8 9 10 1 2 3 4

查找4

当是s[ll]<=s[mid]的时候就是常规的二分

当s[ll]>s[mid]的时候，(k>s[ll]||k<=s[mid])表示k在[ll,mid]内

#include<stdio.h>
#include<iostream>
using namespace std;

int s[109];

int main(){
    int n,k;
    while(scanf("%d",&n)!=EOF){
        int i;
        for(i=0;i<n;i++){
            scanf("%d",&s[i]);
        }
        scanf("%d",&k);

        int ll=0,rr=n-1,mid;
        while(ll<=rr){
            mid=(ll+rr)/2;
            if(s[ll]<=s[mid]){
                if(s[ll]<=k&&k<=s[mid]){
                    rr=mid-1;
                }else{
                    ll=mid+1;
                }
            }else{
                if(k>=s[ll]||k<=s[mid]){
                    rr=mid-1;
                }else{
                    ll=mid+1;
                }
            }
        }

        printf("%d
",s[ll]);
    }

    return 0;
}