二分查找
二分查找模版总结
二分查找是一种在 有序数组 中查找某一特定元素的搜索算法。元素集合有顺序，元素性质有分界点，二分法就可以用来求分界点，并不一定要求集合中元素是不重复的。
可以更快找到分界点
常规写法
int binarySearch(vector<int> &nums, int target) {
int left = 0, right = nums.size() - 1; // 定义 target 在左闭右闭的区间里，[left, right]
while (left <= right) { // 当 left==right，区间 [left, right] 依然有效，所以用 <=
int mid = left + (right - left) / 2); // 防止溢出，结果等同于(left + right)/2
if (nums[mid] > target) {
right = mid - 1; // target 在左区间，所以更新为 [left, mid - 1]
} else if (nums[mid] < target) {
left = mid + 1; // target 在右区间，所以更新为 [mid + 1, right]
} else {
// nums[mid] == target
return mid; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
查看13道真题和解析
