范围概率 用二分查找

游戏里经常用的概率算法，比如随机一个数，看它落在哪段。

这里涉及到随机数之后，看如何查找落在哪个段，可以用二分查找来优化：

#include <iostream>

using namespace std;

int binary_search_nearest(int* arr, int begin, int end, int val){
	if (!arr){
		return -1;
	}
	
	int mid = 0;
	
	while (begin < end){
		mid = (begin + end) / 2;
		
		if (arr[mid] == val){
			return mid;
		}
		else if (arr[mid] < val){
			begin = mid + 1;
		}
		else{
			end = mid - 1;
		}
	}
	
	if (arr[begin] > val){
		--begin;
	}
	
	return begin;
}

int main(){
	int arr[] = {1,2,3,9};
	int res = binary_search_nearest(arr, 0, sizeof(arr)/sizeof(arr[0])-1, 5);
	printf("res:%d\n", arr[res]);
}

范围概率 用二分查找

原文：http://blog.csdn.net/boyxiaolong/article/details/43562461