合并两个有序数组。
 
题目2年前面baidu的时候问的，看起来很简单，写起来还是容易错。当年太菜，写的少。现在写出来不错也不容易。
4最简单的当然是新建一个数组然后一个个往里面放。
这个二分法插入是不额外开辟空间的。感觉复杂度还可以更低，但是弄起来会麻烦。再想想
my @a = (1,3,5,7); my @b = (1,2,4,6,8); my $start = 0; my $end = @a -1 ; for my $t (@b){ print "Tracking $t \n"; my $cur; #binary search do{ $cur = int(($start+$end)/2); $end = $cur if($t<$a[$cur]); $start = $cur if($t>$a[$cur]); if($t == $a[$cur]){ $end = $cur +1; $start = $cur; } } while($end-$start >1); #assign the proper postion $cur = $end; #if the value is larger than the last element in current array, then append thelement to the last ; if($t>$a[$end]){ $cur = $end+1; } #move elements after current postion with distance 1 for(my $i = @a-1; $i >= $cur; $i--){ $a[$i+1] = $a[$i]; } $a[$cur] = $t; $start = $cur; $end = @a-1; print "-----------@a---------------\n"; }