`
kingbinchow
  • 浏览: 123179 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

二分查找的递归算法和非递归算法

阅读更多
好久没写算法,写个二分查找练练手。。。
//recursive
int binarySearch_recursive(int *array,int lowInd ,int highInd,int searchValue){
    int  middleInd =(lowInd+highInd)/2;
    if (lowInd<=highInd) {
         if(array[middleInd]<searchValue){
            //search in top half
            lowInd = middleInd+1;
            return binarySearch(array,lowInd,highInd,searchValue);
        }else if(array[middleInd]>searchValue){
            //search in low half
            highInd = middleInd-1;
            return binarySearch(array,lowInd,highInd,searchValue);
        }else {
            //find value
            return middleInd;
        }
    }else{
        return -1;
    }
        
    return -1;
}

//non recursive function()
int binarySearch_iterative(int *array,int length,int searchValue){
    int low =0,high = length-1;
    int middle =-1;
    while (low<=high) {
        middle =(low+high)/2;
         if(array[middle]>searchValue){
            high = middle-1;
        }else if(array[middle]<searchValue){
            low = middle+1;
        }else {
            //find value
            return middle;
        }
    }
    return -1;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics