2/3の二分検索

/**
         1/3 2/3               
    <==       =====

            (         )：（2/3）^time = n , time = O(log2/3 n);
            ：O(1);
    ======================>
*/

#include<cstdio>
#define NOTFOUND 555555555

//             
int sortedArr[] = {5,7,9,10,11,12,18,22,28};

int myBinary_search(int arr[],int s,int t,int target);

int main()
{
    //          
    int target;
    printf("please input the target you want to find:
");
    scanf("%d",&target);

    //          
    int index = myBinary_search(sortedArr,0,8,target);

    //           
    if(index != NOTFOUND){
         printf("The index of the target number in the array is %d
",index);
    }else{
        printf("The target is not in the array
");
    }
    return 0;

}

//                
//  arr           
//  s             
//  t             
int myBinary_search(int arr[],int s,int t,int target){
    while(s<t){
         //     
        int m = (t-s)/3*2+s;
        if(arr[m] == target)
            return m;
        else if(arr[m] < target)
            s = m + 1;
        else
            t = m - 1;
    }
    return NOTFOUND;
}