二分查找及其变种

二分模板

int binarySearch(vector<int>nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left+(right-left)/2;
        if(key ? nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    //可能还得加判断left，right是否在范围内
    return left or right;
}

标准二分查找

//1.标准二分
int binarySearch_1(vector<int> nums, int key)
{
    int left = 0, right=nums.size()-1;    
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<nums[mid]){
            right = mid-1;
        }else if(key>nums[mid]){
            left = mid+1;
        }else{
            return mid;
        }
    }
    return -1;
}

二分查找变种

1.最后一个小于key的元素

//2.最后一个小于key的元素
int binarySearch_2(vector<int> nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<=nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(right>=0)
        return right;
    else
        return -1;
}

2.第一个大于key的元素

//3.第一个大于key的值
int binarySearch_3(vector<int> nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid  = left + (right-left)/2;
        if(key<nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(left<nums.size())
        return left;
    else
        return -1;
}

3.最后一个小于等于key的元素

//4.最后一个小于等于key的值
int binarySearch_4(vector<int> nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    return right;
}

4.第一个大于等于key的元素

//5.第一个大于等于key的元素
int binarySearch_5(vector<int> nums, int key)
{
    int left = 0,right=nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<=nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    return left;
}

5.第一个与key相等的元素

//6.第一个与key相等的元素
int binarySearch_6(vector<int>nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<=nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(left<nums.size() && nums[left]==key)
        return left;
    return -1;
}

6.最后一个与key相等的元素

//7.最后一个与key相等的元素
int binarySearch_7(vector<int> nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(right>=0 && nums[right]==key)
        return right;
    return -1;
}

完整测试代码

#include<iostream>
#include<vector>
using namespace std;

//1.标准二分
int binarySearch_1(vector<int> nums, int key)
{
    int left = 0, right=nums.size()-1;    
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<nums[mid]){
            right = mid-1;
        }else if(key>nums[mid]){
            left = mid+1;
        }else{
            return mid;
        }
    }
    return -1;
}

//2.最后一个小于key的元素
int binarySearch_2(vector<int> nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<=nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(right>=0)
        return right;
    else
        return -1;
}

//3.第一个大于key的值
int binarySearch_3(vector<int> nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid  = left + (right-left)/2;
        if(key<nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(left<nums.size())
        return left;
    else
        return -1;
}


//4.最后一个小于等于key的值
int binarySearch_4(vector<int> nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    return right;
}

//5.第一个大于等于key的元素
int binarySearch_5(vector<int> nums, int key)
{
    int left = 0,right=nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<=nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    return left;
}

//6.第一个与key相等的元素
int binarySearch_6(vector<int>nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<=nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(left<nums.size() && nums[left]==key)
        return left;
    return -1;
}

//7.最后一个与key相等的元素
int binarySearch_7(vector<int> nums, int key)
{
    int left = 0, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(key<nums[mid]){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(right>=0 && nums[right]==key)
        return right;
    return -1;
}

void test()
{
    //int test_arr[] = {1,2,2,2,3,4,5};//test1
    //int test_arr[] = {2,2,2,4,3};//test2
    //int test_arr[] = {1,2,2,2};//test3
    //int test_arr[] = {1,2,2,2};//test4
    //int test_arr[] = {1,2,3,4};//test5
    //int test_arr[] = {1,2,3,5};//test6
    int test_arr[] = {1,2,2,5};//test7
    vector<int> test_vec(test_arr, test_arr+sizeof(test_arr)/sizeof(int));
    cout<<binarySearch_7(test_vec,3)<<endl;
}

int main()
{
    test();
    return 0;
}