算法

二分查找

二分查找这个非常基础的东西竟然写错了……而且没有意识到，在别的地方debug了半天……

可见基础还是很差，需要多注意。

二分查找：（C++为例，用于多线程归并，查找到的位置要不小于查找的元素，但是左边的元素可以等于查找的元素。查找到的位置可以是数组的右侧下一个元素。）

  • 一种方法：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    		int left = 最左边的那个可能的元素下标, right = 右边可能元素的下标, halflen2;
    while (left <= right) {
    	halflen2 = (left + right) >> 1;
    	if (A[halflen2] > target) {
    		right = halflen2 - 1;
    	}
    	else {
    		left = halflen2 + 1;
    	}
    }
    halflen2 = left;

    这样可以保证每一步中，right所对应的位置不小于target，left对应的位置不大于target。
    这里面没有分开考虑小于和等于，因为现在条件里面不需要……
    但是，如果right和left越界，会怎样呢？

    • 如果left越界，也就是说，当时left已经到了右边界，右边界对应的元素小于等于所要找的；因此会指向最后一个元素的下一个，满足要求。
    • 如果right越界，也就是说，现在right已经到了左边界，所有元素都大于target。但是返回的是left，没有问题。

  • 另一种：

    1
    2
    3
    4
    5
    6
    7
    8
    low = xxx
    high = xxx
    while low < high
       mid = ⌊(low + high)/2⌋
       if x ≤ T[mid]
          high = mid
       else low = mid + 1
    return high

    这里面因为low<high，因此最终会使得low==high，最后返回哪一个无所谓。而且不会发生越界。