二分查找算法的递归与非递归实现(C++)

二分查找又称折半查找， 首先， 假设表中元素是按升序排列， 将
表中间位置的关键字与查找关键字比较：

1. 如果两者相等， 则查找成功；
2. 否则利用中间位置将表分成前、 后两个子表：
   1. 如果中间位置的关键字大于查找关键字， 则进一步查找前一子表
   2. 否则进一步查找后一子表

重复以上过程， 直到找到满足条件的记录， 使查找成功， 或直到子表不存
在为止， 此时查找不成功。

二分查找算法的递归实现

//如果找到target，返回其所在数组下标，如果未找到，返回-1；
int binary_search(std::vector<int> &sort_array,int begin, int end,int target){
    if(begin>end){
	return -1;
    }
    int mid=(begin+end)/2;
    if(target==sort_array[mid]){
	return mid;
    }
    else if(target<sort_array[mid]){
	return binary_search(sort_array,begin,mid-1,target);
    }
    else if(target>sort_array[mid]){
 	return binary_search(sort_array,mid+1,end,target);
    }
}

二分查找算法的非递归实现

//如果找到target，返回其所在数组下标，如果未找到，返回-1；
int binary_search(std::vector<int> &sort_array,int target){
    int begin=0;
    int end=sort_array.size()-1;
    while(begin<=end){
	int mid=(begin+end)/2;
	if(target==sort_array[mid]){
	    return mid;
	}
	else if(target<sort_array[mid]){
	    end=mid-1;
	}
	else
	{
	    begin=mid+1;
	}
    }
    return -1;
}