有序循环数组的查找

浏览数：17 / 时间：2015年06月08日

　　去哪网实习生笔试的第一题。循环有序数组的元素下标的查找，我当时想的居然是用快速排序的Partition( ) 函数，随机的选取一个数作为中轴，将数组排序，这个数的左边数都比它小，右边的数都比它大，然后再用二分查找。最后，最后，我都做完了才反应自己把元素的位置交换了。 /汗，而且题目要求实现的函数的参数是int []arr,没有说明元素的个数，我居然用sizeof(arr)/sizeof(int) 来得到元素个数，傻！int [] 退化成了 int * 成了指针，sizeof()只能是4个字节。

int Search(int arr[],int lo,int hi,int value)
{
    int mi = (lo+hi)>>1;
    if (arr[lo] < arr[mi])   //前半段有序
    {
        //在前半部分
        if (arr[lo] <= value && value >= arr[mi])
        {
            BinarySearch(arr,lo,mi,value);
        }
        else
        {
            Search(arr,mi+1,hi,value);
        }
    }

    //右半段有序
    else
    {
        if (arr[mi] <= value && value <= arr[hi])
        {
            BinarySearch(arr,mi,hi,value);
        }
        else
        {
            Search(arr,lo,mi-1,value);
        }
    }
}


int  BinarySearch(int arr[],int lo,int hi,int value)
{
    //采用迭代，避免递归的内存开销  时间复杂度 O(logn)
    while(lo<hi)
    {
        int mi = (lo+hi)>>1;
        if (arr[mi] > value)  hi = mi;   //前半段[lo,mi)
        else if(arr[mi] < value)  lo = mi+1;  //后半段(mi,hi)
        else  return mi;
    }
    //没找到
    return -1;

}