数据结构学习笔记3
具有对数特点的三个例子：
一、对分查找
给定一个整数X和整数A0，A1，.....AN-1，后者已经预先排序并在内存中，求使得Ai=X的下标i.如果Ai不在数据中，则返回i=-1.
二、欧几里得算法
计算最大公约数的欧几里得算法
这个有一个经过推导得到的结论，若M%N=REF,则REF至多是M的一半。
证明过程：若N<=M/2,则由于余数应该小于N，因此REF<=M/2。
若N>M/2，则这个时候M仅仅含有一个N，那么商为1，因此M-N<M/2,则M-N即为余数，得证。
三，幂运算