算法--二分查找--查找给定条件的值

Michael阿明

发布于 2021-02-20 10:37:09

1.2K0

发布于 2021-02-20 10:37:09

1.数据有序且无重复，查找给定值

/**
 * @description: 数据有序(小到大)且无重复，查找给定值
 * @author: michael ming
 * @date: 2019/4/16 18:54
 * @modified by: 
 */
#include <iostream>
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{
    size_t low = 0, high = n-1;
    while(low <= high)
    {
        size_t mid = low+(high-low)/2;
        if(arr[mid]==num)
            return mid;
        else if(arr[mid] < num)
            low = mid+1;
        else
            high = mid-1;
    }
    return -1;
}
int main()
{
    cout << "数组打印如下：" << endl;
    int arr[N] = {1,2,3,4,5,6,7,8,9,10};
    for(int i = 0; i < N; ++i)
        cout << arr[i] << " ";
    cout << "请输入要查找的数，将返回下标，不存在返回-1：";
    int num;
    cin >> num;
    cout << num << " 的下标是：" << binarySearch_simple(arr,N,num) << endl;
}

2.数据有序且有重复，查找第1个给定的值

/**
 * @description: 查找第一个等于给定值的元素
 * @author: michael ming
 * @date: 2019/4/16 19:19
 * @modified by: 
 */
#include <iostream>
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{
    size_t low = 0, high = n-1;
    while(low <= high)
    {
        size_t mid = low+(high-low)/2;
        if(arr[mid]==num)
        {
            if(mid == 0 || arr[mid-1] != num)   //第一个元素，或者前一个元素不等于num
            	return mid;
            else    //否则，要查找的元素在前面
            	high = mid-1;
        }
        else if(arr[mid] < num)
            low = mid+1;
        else
            high = mid-1;
    }
    return -1;
}
int main()
{
    cout << "数组打印如下：" << endl;
    int arr[N] = {1,1,2,2,4,5,6,7,8,9};
    for(int i = 0; i < N; ++i)
        cout << arr[i] << " ";
    cout << "请输入1个数，将返回查找第一个等于给定值的元素的下标，不存在返回-1：";
    int num;
    cin >> num;
    cout << num << " 的下标是：" << binarySearch_simple(arr,N,num) << endl;
}

3.查找最后一个值等于给定值的元素

/**
 * @description: 查找最后一个值等于给定值的元素
 * @author: michael ming
 * @date: 2019/4/16 20:24
 * @modified by: 
 */
#include <iostream>
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{
    size_t low = 0, high = n-1;
    while(low <= high)
    {
        size_t mid = low+(high-low)/2;
        if(arr[mid]==num)
        {
            if(mid == n-1 || arr[mid+1] != num)   //最后一个元素了，或者后面的不等于num
                return mid;
            else    //否则最后一个元素还在后面
                low = mid+1;
        }
        else if(arr[mid] < num)
            low = mid+1;
        else
            high = mid-1;
    }
    return -1;
}
int main()
{
    cout << "数组打印如下：" << endl;
    int arr[N] = {1,1,2,2,4,5,6,8,8,9};
    for(int i = 0; i < N; ++i)
        cout << arr[i] << " ";
    cout << "请输入要查找的数，将返回最后一个符合的下标，不存在返回-1：";
    int num;
    cin >> num;
    cout << num << " 的下标是：" << binarySearch_simple(arr,N,num) << endl;
}

4.查找第一个大于等于给定值的元素

/**
 * @description: 查找第一个大于等于给定值的元素
 * @author: michael ming
 * @date: 2019/4/16 20:54
 * @modified by: 
 */
#include <iostream>
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{
    size_t low = 0, high = n-1;
    while(low <= high)
    {
        size_t mid = low+(high-low)/2;
        if(arr[mid] >= num) //当找到要求的值时
        {
            if(mid == 0 || arr[mid-1] < num)    //判断是第一个元素，或者前面的比我小
                return mid; //当前满足
            else    //否则满足要求的还在前面
                high = mid-1;
        }
        else if(arr[mid] < num)
            low = mid+1;
    }
    return -1;
}
int main()
{
    cout << "数组打印如下：" << endl;
    int arr[N] = {1,2,2,4,5,6,7,8,9,10};
    for(int i = 0; i < N; ++i)
        cout << arr[i] << " ";
    cout << "请输入一个数，将返回第一个大于等于它的下标，不存在返回-1：";
    int num;
    cin >> num;
    cout << num << " 的下标是：" << binarySearch_simple(arr,N,num) << endl;
}

5.查找最后一个小于等于给定值的元素

/**
 * @description: 查找最后一个小于等于给定值的元素
 * @author: michael ming
 * @date: 2019/4/16 23:09
 * @modified by: 
 */
#include <iostream>
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{
    size_t low = 0, high = n-1;
    while(low <= high)
    {
        size_t mid = low+(high-low)/2;
        if(arr[mid] > num)
            high = mid-1;
        else if(arr[mid] <= num)
        {
            if(mid == n-1 || arr[mid+1] > num)  //最后一个元素，或者后面的比它大了
                return mid; //它是最后一个小于等于的
            else
                low = mid+1;    //否则后面还有满足的，下限往上加
        }
    }
    return -1;
}
int main()
{
    cout << "数组打印如下：" << endl;
    int arr[N] = {1,2,2,4,5,6,7,10,10,10};
    for(int i = 0; i < N; ++i)
        cout << arr[i] << " ";
    cout << "请输入一个数，返回最后一个小于等于给定值的元素的下标，不存在返回-1：";
    int num;
    cin >> num;
    cout << num << " 的下标是：" << binarySearch_simple(arr,N,num) << endl;
}

6.查找IP归属（利用上面#5代码）

/**
 * @description: 查找ip地址归属，找到最后一个区间开始地址<=ip的
 * @author: michael ming
 * @date: 2019/4/16 23:38
 * @modified by: 
 */
#include <iostream>
#include "binarySearch_findLastLessNum.cpp"
int main()
{
    int start[5] = {101,201,301,401,501};   //假设为ip起始地址（A,B,C,D,E）
    int end[5] =    {200,300,400,500,600};  //对应ip终止地址
    size_t ip;
    while(1)
    {
        std::cout << "请输入要查询的ip: ";
        std::cin >> ip;
        int index = binarySearch_simple(start,5,ip);    //在ip区间头里查找最后一个<=我的
        if(index != -1 && ip <= end[index])
            switch(index)
            {
                case 0:
                    std::cout << "ip in city A"<< std::endl;
                    break;
                case 1:
                    std::cout << "ip in city B"<< std::endl;
                    break;
                case 2:
                    std::cout << "ip in city C"<< std::endl;
                    break;
                case 3:
                    std::cout << "ip in city D"<< std::endl;
                    break;
                case 4:
                    std::cout << "ip in city E"<< std::endl;
                    break;
            }
        else
            std::cout << "ip not found!" << std::endl;
    }
}

7.循环有序数组，查找给定值

例如：4,5,6,7,1,2,3 循环数组性质：以数组中间点为分区，数组分成一个有序数组和一个循环有序数组。

如果首元素 arr[low] < arr[mid]，左半部分：有序，右半部分：循环有序；如果首元素 arr[low] > arr[mid]，右半部分：有序，左半部分：循环有序；判断查找的数是否在有序的半边范围内，更新上下限时间复杂度为 O(logN)。

/**
 * @description: 循环有序数组，查找给定值
 * @author: michael ming
 * @date: 2019/4/17 0:25
 * @modified by: 
 */
#include <iostream>
#define N 10
int circular_Arr_BS(int *arr, size_t n, int num)
{
    size_t low = 0, high = n-1;
    while(low <= high)
    {
        size_t mid = low+(high-low)/2;
        if(arr[mid] == num)
            return mid;
        if(arr[mid] < arr[low]) //转折点在左边,右边有序
        {
            if(arr[mid] <= num && num <= arr[high]) //数据在右边
                low = mid+1;
            else
                high = mid-1;
        }
        else    //转折点在右边，左边有序
        {
            if(arr[low] <= num && num < arr[mid])   //数据在左边
                high = mid-1;
            else
                low = mid+1;
        }
    }
    return -1;
}
int main()
{
    int arr[N] = {4,5,6,7,8,9,10,1,2,3};
    size_t mid = (N-1)/2;
    int num;
    std::cin >> num;
    std::cout << circular_Arr_BS(arr,N,num);
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/04/17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

算法--二分查找--查找给定条件的值

算法--二分查找--查找给定条件的值

1.数据有序且无重复，查找给定值

2.数据有序且有重复，查找第1个给定的值

3.查找最后一个值等于给定值的元素

4.查找第一个大于等于给定值的元素

5.查找最后一个小于等于给定值的元素

6.查找IP归属（利用上面#5代码）

7.循环有序数组，查找给定值

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐