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:\n");
    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\n",index);
    }else{
        printf("The target is not in the array\n");
    }
    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;
}