各位好呀， 我转专业至计科， 开始在大二学习算法。 为以后的竞赛之路做准备。
想把自己的所学所想记录在博客上， 欢迎大家来讨论。
向量 概念向量是线性数组的一种抽象与泛化， 它也是由具有线性次序的一组元素构成。如 V = { V 0 , V 1 , V 2 , . . . V n − 1 } V={V_0,V_1,V_2,...V_{n-1}} V={V0,V1,V2,...Vn−1},其中的元素由秩相互区分。 各元素的秩互异，且均为[0,n)的整数。 向量有时也被称作线性表。
区间定义方法- 左闭右开， 即[left, right)
- 左闭右闭， 即[left, right]
鉴于向量秩的定义，我们常常使用左闭右开的区间定义方法。
对此， 有序向量的二分查找算法， 对区间定义的方法十分敏感， 我的这第一篇文章想对二分查找算法进行详细的阐述。
二分查找算法力扣相关算法链接
class Solution {
public:
int search(vector& nums, int target) {
int left = 0, right = nums.size(); //定义左右区间， 注意right对应上图的end，数组最后一个有效位置的下一个
while( left < right)
{
//寻找中间位置， 等同middle = left + (right - left) >> 1
int middle = (left + right) >> 1;
// target在秩为middle左方， 调整为在[left,middle)寻找
if(target < nums[middle]) right = middle;
//target在秩为middle右方， 调整为在[middle+1, right)中寻找
else if(nums[middle] < target) left = middle + 1;
else return middle; //命中目标，返回目标所在秩
}
return -1; // 未命中目标， 返回-1
}
};
以上代码很好阐述了二分查找算法的精髓所在。 其中 target < nums[middle] 与 nums[middle] < target 的代码书写风格主要是体现在 算术符 与运算数的结合顺序， 很好的体现了target 在左与target在右的印象。 邓俊辉的数据结构非常的棒，给大家安利下。
复杂度随着迭代的不断深入， 有效的寻找宽度按1/2 的 比例 以几何级数的速度递减。 于是， 经过至多 l o g 2 ( r i g h t − l e f t ) log_2(right - left) log2(right−left) 步，算法必然终止。 鉴于每步迭代只需常数时间， 故
$O(log_2(right-left)) $
步迭代只需常数时间， 故
O ( l o g 2 ( r i g h t − l e f t ) ) = O ( l o g n ) O(log_2(right-left)) =O(logn) O(log2(right−left))=O(logn)
