认识复杂度和简单排序

1. o(n2) 复杂度：

• 选择排序，冒泡排序
• 额外空间
• 插入排序 （重点） ： 1 你不比你前一个数小 2.你前面没数了 --玩扑克
• 时间复杂度永远按照最差状况来估计

2. 二分法

三道题：
1.有序数组中，找某个数是否存在
2.有序数组中，找>=某个数最左侧的位置
3.局部最小（小于左边和右边且相邻位置不等）

第一题： O(logN)
第二题： O(logN) 第三题：
中点：mid = l+((r-l)>>1) 中点防止溢出
mid = l+ (r-l)/2
a/2 也可以写成a>>1（a是正数）

7 00111
7/2=3
3 00011
所以任何正数除以2等同于这个数右移一位  
位运算比算术运算，尤其除的运算

“>>”：右移动，高位用符号位来补: 譬如00111 变成 00011 “>>>”：右边移位，但是最高位都用0来补

1. 判断0位置和N位置是不是最小，如果不是判断mid是不是最小
2. mid位置，如果比左边大，保留左边判断mid是不是最小

异或运算

无进位相加

01011000
10111010
---------
11100010  

O^N == N
N^N == 0
异或运算满足交换律和结合律

1. 不用额外变量，如何交换两个数

a=a^b   
b=a^b
a=a^b

以上代码就可以交换ab的数值：必须保证a和b在内存里是两块。
如果他们在内存里是一块的时候，那么ab就都变成了0 了。

2. 一个数组中一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数

所有数与0依次异或，得到的数就是这个数。

3. 一个数有两种数出现了奇数次，其他都是偶数，如何找到这两个数

• 找个数依次异或，例如eor =a^b
• a !=b,则eor ！=0
• 则eor中必须有1
• 假设eor第四位是1，则a和b在第四位不同
• 再准备一个变量eor'再异或一遍，只异或第四位上不为0的数上。则得出来的结果一定是a或者b

for(int num :arr){
    eor ^=num;
}

如何提取出来最右边第一个“1” 取反+1和自己&：

eor & (~eor+1)

4. 对数器的概念和使用 oj：online judge

1. 有一个你想要测的方法a
2. 实现复杂度不好但是容易实现的方法b
3. 实现一个随机样本产生器
4. 把方法a和方法b跑相同的随机样本，看看得到的结果一样不
5. 如果有一个随机样本使得对比结果不一致，打印样本进行人工干预，改对方法a或者方法b
6. 当样本数量很多时，对比测试依然正确，确定方法a已经正确