二分搜索的递归与非递归实现

二分搜索的非递归写法很直白，就是区间问题，维护三个变量从而达到搜索的目的，代码如下。

int Binary_Search(SSTable L, ElemType key) {
    int low = 0, high = L.TableLen - 1,mid;//low和high是下标大小。
    while (low <= high) {
        mid = (low + high) / 2;
            if (L.elem[mid] == key) {
                return mid;
            }
            else if (L.elem[mid] > key) {//要查找的key值小于mid下标对应的值，边界向mid的左边变化，低边界不变，高边界变化到mid左边。所以high=mid-1。
                high = mid - 1;//右边界变换为 mid - 1
            }
            else {
                low = mid + 1;//左边界变换 mid + 1 
            }
    }
    return -1;
}

但是 还有一种是非递归写法，体现子问题的思想，代码如下：

int BinarySearch(int* nums,int target,int left,int right) {//二分递归实现。
    if(left > right) return -1;//递归出口，二分结束条件。即左边大于右边。
    int mid = (left + right) >> 1;
    if(nums[mid] == target) return mid;//递归出口，二分找到后直接返回mid。

    if(nums[mid]<target) return BinarySearch(nums,target,mid+1,right);
    else{
        return BinarySearch(nums,target,left,mid-1);
    }

}

int search(int *nums,int numSize,int target){
    return BinarySearch(nums,target,0,numSize-1);
}

int main(){
    int arr[] = {1,3,4,6,7,8,10,11,13,15},target=10;
    printf("%d/n", search(arr,10,target));
}

通过递归划分区间去解决小问题，最后返回就可以解决整个问题。