Sony A850 officially discontinued# PhotoGear - 摄影器材
x*w
1 楼
Merge两个sorted array, 长度分别为m和n, array的特征如下:
a => 1,2,3,4 ...1001, 9876283, 9876285, 9876293, 9876297, ...9993456, ....
b => 7,10,13,14,... , 8873, 8875, 5678999871, 5678999873, 5678999874 ....
很显然sorted array会有一个big jump. 在发现一个big jump的时候对另一个数组不需
要再一个个的挪，可以做二分。(j到m-1做二分)
也可以这么做，看j+1, j+2, j+4, j+8, j+16 ..., 找到j + 2^x使得b[j+2^x] > a[i]
, 然后再在b[j .. j+2^x]里做二分找到刚好大于a[i]的数。
问题是：
这里的x取什么值最好，一定是2吗？
什么情况下，比如取3比2要更优？
a => 1,2,3,4 ...1001, 9876283, 9876285, 9876293, 9876297, ...9993456, ....
b => 7,10,13,14,... , 8873, 8875, 5678999871, 5678999873, 5678999874 ....
很显然sorted array会有一个big jump. 在发现一个big jump的时候对另一个数组不需
要再一个个的挪，可以做二分。(j到m-1做二分)
也可以这么做，看j+1, j+2, j+4, j+8, j+16 ..., 找到j + 2^x使得b[j+2^x] > a[i]
, 然后再在b[j .. j+2^x]里做二分找到刚好大于a[i]的数。
问题是：
这里的x取什么值最好，一定是2吗？
什么情况下，比如取3比2要更优？
