二分法（查找元素及其上界与下界）

利用二分法去查找某个元素效率高，将所要查找的元素称为key，有时利用二分法进行查找key的上界与下界，下界通常为key第一次出现的位置，上界通常为第一个大于key的位置。

1 寻找key的代码：

int find(int array[], int len,int key) {
int left = 0, right = len - 1 ;    // attention !
while (left <= right) {            // attention !
int mid = left + ((right - left)>>1); 
if (array[mid] == key)  // !!
return mid;
else if(array[mid] < key)
            left = mid + 1;
else
            right = mid - 1;
    }

return array[left]==key?left:-1;
}

2 寻找key下界的代码：

int find_lowerbound(int array[], int len,int key) {
int left = 0, right = len ;    // attention !
while (left < right) {
int mid = left + ((right - left)>>1); 
if (array[mid] < key)  // !!
            left = mid + 1;
else
            right = mid;
    }

return left<len && array[left] == key ? left:-1;
}

3 寻找key上界的代码：

int find_upperbound(int array[], int len, int key) {
int left = 0, right = len;    // attention !
while (left < right) {
int mid = left + ((right - left) >> 1);
if (array[mid] <= key)
            left = mid + 1;
else
            right = mid;
    }

return left >= 0 && array[left ] == key ? left  : -1;
}