02-D4

(d4) 有序向量: 二分查找(改进)
-----------------------------

# 版本B, 改进思路:
	>* 左右转向成本平衡：
		无论向左还是向右进行一次比较。
	
	>* 轴点mi为中点, 每查找深入一层, 问题规模缩减一半
		1, e <  x: e若存在则在左侧子区间S[lo, mi), 可递归深入
		2, x <= e: e若存在则在右侧子区间S[mi, hi), 可递归深入
		只有当hi - lo = 1时, 判断元素是否命中。
		
# 实现:
	>* 我的尝试
		=========================  source code =======================
		template <typename T>
		Rank Vector<T>::binBlcSearch(T* elem, T const& e, Rank lo, Rank hi) const {
			// 二分平衡查找算法
			while (1 < hi - lo) {
				int mi = (lo + hi) >> 1;          // 轴点为中点
				if (e < elem[mi]) hi = mi;        // 深入左区间
				else if (elem[mi] <= e) lo = mi;  // 深入右区间
			}
			// hi - lo == 1, 判断当前元素是否命中
			if (e == elem[lo]) return lo;
			else               return -1;
		}
		===========================================================
		思路上无问题, 但代码可以简化。
		
	>* 更为简洁的写法
		=====
	    template <typename T>
		Rank Vector<T>::binBlcSearch(T* elem, const T& e, Rank lo, Rank hi) const {
			while (1 < hi - lo) {
			int mi = (lo + hi) >> 1;               // 轴点为中点
			(e < elem[mi]) ? hi = mi : lo = mi;    // 在哪个区间上深入
			}    // 退出循环时, 区间长度1, elem[lo]为有效元素
			return (e == elem[lo])? lo: -1;
		}        // 相对于binSearch A版本, 最好(坏)情况下更坏(好)
		====
		
		1, 两种情况if...else 用以下代替
			(cond)? expr1 : expr2;
		2, 在其中使用返回语句
			(cond) ? return expr1 : return expr2;    // ERROR!!
			return (cond) ? expr1 : expr2;           // Right!!
----------------------------------------------------------------------------------

# 语义约定
	>* 为什么要语义约定?
		便于其他高阶操作的调用。
		v.insert(1 + search(e, lo, hi), e);
			：在找到元素索引的下个索引处插入。
	
	>* 思路
		1, 有多个元素匹配时, 返回最大秩(不大于e的最后一个元素秩)
		2, 未匹配元素时, 返回小于e的最大者秩(含哨兵[lo - 1])
	
	>* 实现, 版本C
		>* 我的尝试
		将原来的 return (e == elem[lo]) ? lo : -1; 改为:
		============= source code ============================
		if (e == elem[lo]) {  // 存在匹配
			while (elem[lo+1] == elem[lo]) lo++;  // 返回最大秩
			return lo;
		} else {  // 无匹配
			return (e < elem[lo]) ? lo - 1 : lo;  // 返回小于e的最大者秩
		}
		=======================================================
		一次while循环找到最大匹配的索引, 一次判断确定不匹配时返回秩
		
		>* 更优解
		==================== source code ===========================
		template <typename T>
		Rank Vector<T>::binBlcSearch(T* elem, const T& e, Rank lo, Rank hi) const {
			while (lo < hi) {  // 区间缩短至0
				int mi = (lo + hi) >> 1;                   // 轴点为中点
				(e < elem[mi]) ? hi = mi : lo = mi + 1;    // [lo, mi), (mi, hi)
			}    // 退出循环时, 区间长度0, A[lo = hi]为大于e的最小元素
			return --lo;    // 故lo-1 为不大于e的最大秩
		}      // 相对于binSearch A版本, 最好(坏)情况下更坏(好)
		=============================================================
	
	>* 更优解实现分析
		>* 差别
			1, 循环结束区间宽度0, 而非1
			2, 转入右侧子向量时, 左边界取作mi + 1而非mi, elem[mi]看似遗漏?
			3, 无论成功与否, 返回秩序严格符合定义的语义接口。
			4, 和我的实现比起来, 无需多余的while和if判断
----------------------------------------------------------------------------------

# 版本C, 正确性:
	>* 不变性:
		A[0, lo) <= e < A[hi, n)          // A[hi] 总是大于e的最小者
	>* 初始
		lo = 0且hi = n, A[0, lo) = A[hi, n) = 空集, 自然成立
	>* 数学归纳两种情况,
		这两种情况不是很清楚。以后可以回过头来看看。