二分法
最近开始学习《数据结构与算法》这门课程，感觉真就脑筋急转弯...
总感觉脑子里没有想法，我想，应对之策有两个：
- 首先得着手开始写，先跑起来再来解决性能问题
- 其次就是尽可能发现归纳一些通用的trick
这篇文章是应对之策的第二种的一个例子吧
将一个数组按某个标准分为两组
实验课遇到一个题目要求把数组里的奇数放左边，偶数放右边，时间复杂度是O(n)
我一看，噢，这不就是我前段时间心心念念的Quicksort快排算法中第一步，先把数组分两堆么？
步骤我都知道，快排里无非是选定一个数，将它取出，以它做参照，大的放一边，小的放一边么？
这道题里，无非就是简化一下，直接选最右边的数出来，参照标准是mod 2等不等于0
但问题来了，数组要怎么移动呢？
...这就是学习不够深入了，隐约记得取出这个数是挖了个空，然后填坑，最后坑里放回取出的数字，就完事了
问题就出在这个数组移动上
刚开始我想既然o(n)，何不直接移到底，遇到偶数往坑里填（坑在最右边），可是留出来的新坑放什么呢？
放偶数？可是不是在左边么
放奇数？好像可行，但是遇到连续几个偶数之后的奇数就麻烦了..
也许这种思路应该摒弃，这种总是对自己代码做什么能不能做好没什么概念，也没什么信心的情况，不知道怎么解决好
一波操作以后，实在不会，上网搜索了一下
发现数组元素的移动是遵循这样一个思路（事实上这道题老师的标准答案也是这个思路）
以这题为例，数组分成左右两边
“左边放奇数，右边放偶数”这句话
其实就等价于
“左边扔掉偶数，右边扔掉奇数”
也就是说，在左边找偶数，在右边找奇数
左右边对应的元素互换就好
因此，设置两个指针指向两边的头，分别对两边进行遍历，直到两个指针碰到一起，代表对整个数组的遍历已经完成
也就是确保了左边全都是奇数，右边全都是偶数
另外一个地方在于怎么选择遍历的顺序，也是其中一个令我迷惑的地方
“左边放奇数，右边放偶数”
最开始取出最右边，那就从左边开始，
左边扔掉一个偶数放坑里，然后坑就在左边了
换到右边遍历，右边扔掉一个奇数放左边，坑就在右边了
如此循环，直到i==j
代码其实很简单，关键是理解这个思路吧，下面是Code
void SeqList::Adjust(){
int left=-1,right=length-1;
int t=data[length-1];
int cur=length-1;
while(right!=left){
while(data[++left]%2!=0&&right!=left);
data[cur]=data[left];
cur=left;
while(data[--right]%2==0&&right!=left);
data[cur]=data[right];
cur=right;
}
data[right]=t;
}
我想也许这种转化问题的方法也许是应对之策之三？
找最接近的2的幂
2022.10.9更新：这篇文章决定把它整成一个二分法专题了，感觉这个二分法远比自己想象的有意思，哈哈。被数据结构老师上课点名点到玩猜数字，她说二分法这种思想应该贯彻生活（程序员的浪漫~
JAVA课上，老师给的阅读材料里有篇讲Hashmap原理的，其中关于Map数组容量，Hashmap的实现了一个找出大于等于一个数的最小2的幂的方法。
static final int tableSizeFor(int cap){
int n=cap-1;
n |= n>>1;
n |= n>>2;
n |= n>>4;
n |= n>>8;
n |= n>>16;
return n+1;
}
这个方法一眼看过去不禁眼熟，这不就我前些天研究的那个玩意，一看：16 8 4 2 1，妥妥应该二分法，但是还是搞不明白。
后来发现这个二分法也很妙，它为了确保所有数位上都是1（因为最后+1，就能变成10000...就是2的n次幂）
先是右移1位，这1位关键在于它移动了头部，因为这个数最高位上一定是1
移动1次，再或运算，就确保了高2位都是1，
右移2位，确保高4位都是1
...
以此类推，这个数所有的位都是1
那么为什么要先-1，因为最后要+1，对于已经是2的幂的数来说，如果不这么做的话，就会变成比这个数更大的2的幂，所以加入这个以修正该问题