二分查找及其变形

二分查找时间复杂度

　　O(logn)

标准型：在增序数组中查找一个目标数的下标

1号版本：

初始值：left=0, right=nums.size()，right其实下标越界

循环条件：left<right

赋值公式：mid=left + (right - left) / 2, left=mid+1, right=mid，mid为中点或偏右

 1 int find(vector<int>& nums, int target) 
 2 {
 3     int left = 0, right = nums.size();
 4     while (left < right) 
 5     {
 6         int mid = left + (right - left) / 2;
 7         if (nums[mid] == target) 
 8         　　return mid;
 9     　　 else if (nums[mid] < target) 
10         　　left = mid + 1;
11     　　 else 
12     　　 　　right = mid;
13     }
14     return -1;
15 }

递归版本：

 1 int find(vector<int>& nums, int target)
 2 {
 3     return find(nums, 0, nums.size(), target);
 4 }
 5 
 6 int find(vector<int>& nums, int left, int right, int target)
 7 {
 8     if (left >= right)
 9         return -1;
10     int mid = left + (right - left) / 2;
11     if (nums[mid] == target)
12         return mid;
13     else if (nums[mid] < target)
14         return find(nums, mid + 1, right, target);
15     else
16         return find(nums, left, mid, target);
17 }

2号版本：

初始值：left=0, right=nums.size()-1

循环条件：left<=right，看清是等号

赋值公式：mid=left + (right - left) / 2, left=mid+1, right=mid-1，mid为中点或偏左

 1 int find(vector<int>& nums, int target)
 2 {
 3     int left = 0, right = nums.size()-1;
 4     while (left <= right)
 5     {
 6         int mid = left + (right - left) / 2; 
 7         if (nums[mid] == target)
 8             return mid;
 9         else if (nums[mid] < target)
10             left = mid + 1;
11         else
12             right = mid - 1;
13     }
14     return -1;
15 }

变型（以下变型代码均是在1号版本基础上修改）

变型一：在增序数组中寻找第一个大于等于目标数的数的下标

此种变型在寻找相同元素的第一个元素的下标时很有用，对应c++STL中的lower_bound
目标数有可能在数组中，也有可能不在
去除nums[mid]==target的判断，返回left或right均可，如果数组中不存在大于等于目标数的数，那么将返回nums.size()

int find(vector<int>& nums, int target)
{
    int left = 0, right = nums.size();
    while (left < right)//最后出来时，left=right，随便返回哪个均可
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

变形二：在增序数组中寻找最后一个小于目标数的数的下标

在变型一的基础上只需要返回right-1即可
如果数组中不存在小于目标数的数，那么将返回-1

变形三：在增序数组中寻找第一个大于目标数的数的下标

对应c++STL中的upper_bound
目标数有可能在数组中，也有可能不在
在变型一的基础上将nums[mid] < target改成nums[mid] <= target，返回left或right均可，如果数组中不存在大于目标数的数，那么将返回nums.size()

int find(vector<int>& nums, int target)
{
    int left = 0, right = nums.size();
    while (left < right)//最后出来时，left=right，随便返回哪个均可
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

变形四：在增序数组中寻找最后一个小于等于目标数的数的下标

此种变型在寻找相同元素的最后一个元素的下标时很有用
在变型三的基础上只需要返回right-1即可
如果数组中不存在小于等于目标数的数，那么将返回-1