算法模版 – 查找

查找算法中，惯用的二分查找是得学会的。

二分查找

二分查找的难点在于区间的选取，我们默认全局使用左闭右开。

三个细节(前俩都是因为左闭右开）：

• 1 while(left < right)
• 2 right = middle, left = middle + 1
• 3 int middle = left + (right – left) / 2; 这么计算可以防止溢出

int two_find(vector &nums, int target) {
	int left = 0, right = nums.size();
	while (left < right) { int middle = (left + right) / 2; if (nums[middle] == target) return middle; else if (nums[middle] > target)
			right = middle;
		else if (nums[middle] < target)
			left = middle + 1;
	}
	return -1;
}



int main() {
	vector nums = {12, 43, 21, 47, 87, 9, 13, 40};
	int output = two_find(nums, 21);
	cout << output << endl;
	return 0;
}