本文共 6835 字，大约阅读时间需要 22 分钟。

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

/** * @description: 数据有序(小到大)且无重复，查找给定值 * @author: michael ming * @date: 2019/4/16 18:54 * @modified by:  */#include 
   
    #define N 10using 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 
   
    #define N 10using 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 
   
    #define N 10using 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 
   
    #define N 10using 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 
   
    #define N 10using 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 
   
    #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]，左半部分：有序，右半部分：循环有序；

/** * @description: 循环有序数组，查找给定值 * @author: michael ming * @date: 2019/4/17 0:25 * @modified by:  */#include 
   
    #define N 10int 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;}
   

转载地址：https://michael.blog.csdn.net/article/details/89339488 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！