首页 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
资讯 业界资讯 软件杂谈 编程开发 网站建设 网络观查 搜索引擎 移动应用 网站运营 网络地图
开发 移动开发 Web前端 架构设计 编程语言 互联网 数据库 系统运维 云计算 开发杂谈
[编程语言] [经典面试题]二分查找问题汇总
[经典面试题]二分查找问题汇总

1.【给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]等于target,不存在则返回-1。】

【题目】

给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]等于target,不存在则返回-1。
【分析】

此题也就是求target在数组中第一次出现的位置。这里可能会有人想先直接用原始的二分查找,如果不存在直接返回-1,
如果存在,然后再顺序找到这个等于target值区间的最左位置,这样的话,最坏情况下的复杂度就是O(n)了,没有完全发挥出二分查找的优势。
这里的解法具体过程请参考实现代码与注释。
【代码】

/*********************************
*   日期:2015-01-05
*   作者:SJF0115
*   题目: 给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]等于target,不存在则返回-1
*   博客:
**********************************/
#include <iostream>
using namespace std;

int BinarySearch(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start < end){
        int mid = (start + end) / 2;
        if(A[mid] < target){
            start = mid + 1;
        }//if
        else{
            end = mid;
        }//else
    }//while
    // 目标不存在的情况
    // 此时start = end
    if(A[start] != target){
        return -1;
    }//if
    else{
        return start;
    }
}

int main(){
    int A[] = {2,3,4,4,4,4,4,5,6,7,8};
    cout<<BinarySearch(A,11,4)<<endl;
    return 0;
}

/*********************************
*   日期:2015-01-05
*   作者:SJF0115
*   题目: 给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]等于target,不存在则返回-1
*   博客:
**********************************/
#include <iostream>
using namespace std;

int BinarySearchMin(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素左边元素等于目标元素
            if(mid - 1 >= 0 && A[mid - 1] == target){
                end = mid - 1;
            }//if
            else{
                return mid;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}

int main(){
    int A[] = {4,4,4,4,4,5,6,7,8};
    cout<<BinarySearchMin(A,11,4)<<endl;
    return 0;
}

2.【给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A[i]等于target,不存在则返回-1】

【题目】

给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A[i]等于target,不存在则返回-1
【分析】

和上题类似
【代码】

/*********************************
*   日期:2015-01-05
*   作者:SJF0115
*   题目: 给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A[i]等于target,不存在则返回-1
*   博客:
**********************************/
#include <iostream>
using namespace std;

int BinarySearchMax(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素右边元素等于目标元素
            if(mid + 1 < n && A[mid + 1] == target){
                start = mid + 1;
            }//if
            else{
                return mid;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}

int main(){
    int A[] = {2,3,4,4,4,4,4,5,6,7,8};
    cout<<BinarySearchMax(A,11,4)<<endl;
    return 0;
}

3.【给定一个有序(非降序)数组A,可含有重复元素,小于target的最大元素的位置,不存在则返回-1】

【题目】

给定一个有序(非降序)数组A,可含有重复元素,小于target的最大元素的位置,不存在则返回-1
【分析】

这个问题可以转换为给定一个有序(非降序)数组A,可含有重复元素,等于target的最小元素的前一个,不存在则返回-1
【代码】

/*********************************
*   日期:2015-01-05
*   作者:SJF0115
*   题目: 给定一个有序(非降序)数组A,可含有重复元素,小于target的最大元素的位置,不存在则返回-1
*   博客:
**********************************/
#include <iostream>
using namespace std;

int BinarySearch(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    int index;
    // 求含重复元素中等于target的最小位置
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素左边元素等于目标元素
            if(mid - 1 >= 0 && A[mid - 1] == target){
                end = mid - 1;
            }//if
            else{
                return mid-1;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}

int main(){
    int A[] = {1,2,4,4,4,4,4,5,6,7,8};
    cout<<BinarySearch(A,11,4)<<endl;
    return 0;
}

4.【给定一个有序(非降序)数组A,可含有重复元素,大于target的最小元素的位置,不存在则返回-1】

【题目】

给定一个有序(非降序)数组A,可含有重复元素,大于target的最小元素的位置,不存在则返回-1
【分析】

这个问题可以转换为给定一个有序(非降序)数组A,可含有重复元素,等于target的最大元素的后一位置,不存在则返回-1
【代码】

/*********************************
*   日期:2015-01-05
*   作者:SJF0115
*   题目: 给定一个有序(非降序)数组A,可含有重复元素,大于target的最小元素的位置,不存在则返回-1
*   博客:
**********************************/
#include <iostream>
using namespace std;

int BinarySearch(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    int index;
    // 求含重复元素中等于target的最大位置
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素右边元素等于目标元素
            if(mid + 1 < n && A[mid + 1] == target){
                start = mid + 1;
            }//if
            else{
                return (mid + 1 >= n)?-1:mid+1;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}

int main(){
    int A[] = {1,2,4,4,4,4,4,5,6,7,8};
    cout<<BinarySearch(A,11,4)<<endl;
    cout<<BinarySearch(A,11,5)<<endl;
    cout<<BinarySearch(A,11,8)<<endl;
    return 0;
}

5.【给定一个有序(非降序)数组A,可含有重复元素,求target在数组中出现的次数】

【题目】

给定一个有序(非降序)数组A,可含有重复元素,求target在数组中出现的次数
【分析】

上面已经求出给定一个有序(非降序)数组A,可含有重复元素,求等于target最小位置和最大位置。
【代码】

/*********************************
*   日期:2015-01-05
*   作者:SJF0115
*   题目: 给定一个有序(非降序)数组A,可含有重复元素,求target在数组中出现的次数
*   博客:
**********************************/
#include <iostream>
using namespace std;
// 求等于target的最小元素位置
int BinarySearchMin(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素左边元素等于目标元素
            if(mid - 1 >= 0 && A[mid - 1] == target){
                end = mid - 1;
            }//if
            else{
                return mid;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}
// 求等于target的最大元素位置
int BinarySearchMax(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start <= end){
        int mid = (start + end) / 2;
        // 中间元素等于目标
        if(A[mid] == target){
            // 如果中间元素右边元素等于目标元素
            if(mid + 1 < n && A[mid + 1] == target){
                start = mid + 1;
            }//if
            else{
                return mid;
            }//else
        }//if
        else if(A[mid] > target){
            end = mid -1;
        }//else
        else{
            start = mid + 1;
        }
    }//while
    return -1;
}

int BinarySearchCount(int A[],int n,int target){
    int min = BinarySearchMin(A,n,target);
    int max = BinarySearchMax(A,n,target);
    // 没有
    if(min == -1){
        return 0;
    }//if
    int count = max - min + 1;
    return count;
}

int main(){
    int A[] = {1,2,4,4,4,4,4,5,6,7,8};
    cout<<"Count->"<<BinarySearchCount(A,11,4)<<endl;
    return 0;
}



 此文从网络中自动搜索生成,不代表本网站赞成被搜索网站的内容或立场    查看原文
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 新闻资讯 小游戏 Chinese Culture 股票 三丰软件 开发 中国文化 网文精选 阅读网 看图 日历 万年历 2018年9日历
2018-9-26 14:50:22
 
  网站联系 软件世界网-www.sjsjw.com ©2014 蜀ICP备06016416号 三峰网旗下网站