`
SunnyYoona
  • 浏览: 361754 次
社区版块
存档分类
最新评论

[经典面试题]二分查找问题汇总

 
阅读更多

[算法]二分查找算法

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;
}

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

【题目】

给定一个有序(非降序)数组A,可含有重复元素,求target在数组中出现的下标范围

【分析】

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

具体参考:[LeetCode]34.Search for a Range

【代码】
/*********************************
*   日期:2015-01-24
*   作者:SJF0115
*   题目: 34.Search for a Range
*   网址:https://oj.leetcode.com/problems/search-for-a-range/
*   结果:AC
*   来源:LeetCode
*   博客:
**********************************/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> result;
        if(n <= 0){
            return result;
        }//if
        // 目标元素的最小位置
        int left = searchStartRange(A,n,target);
        // 目标元素的最大位置
        int right = searchEndRange(A,n,target);
        result.push_back(left);
        result.push_back(right);
        return result;
    }
private:
    // 目标元素的最小位置
    int searchStartRange(int A[],int n,int target){
        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;
                }
            }
            // 目标位于右半部分
            else if(A[mid] < target){
                start = mid + 1;
            }//
            // 目标位于左半部分
            else{
                end = mid - 1;
            }
        }//while
        return -1;
    }
    // 目标元素的最大位置
    int searchEndRange(int A[],int n,int target){
        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(A[mid] < target){
                start = mid + 1;
            }//
            // 目标位于左半部分
            else{
                end = mid - 1;
            }
        }//while
        return -1;
    }
};

int main(){
    Solution solution;
    int A[] = {1};
    int n = 1;
    int target = 0;
    vector<int> result = solution.searchRange(A,n,target);
    // 输出
    for(int i = 0;i < result.size();++i){
        cout<<result[i]<<endl;
    }//for
    return 0;
}

7.【给定一个有序(非降序)数组A,不含重复元素,求target在数组中下标位置,如果找不到,则返回插入位置

【题目】

给定一个有序(非降序)数组A,可含有重复元素,求target在数组中下标位置,如果找不到,则返回插入位置。

【分析】

具体参考:[LeetCode]35.Search Insert Position

【代码】
/*********************************
*   日期:2015-01-24
*   作者:SJF0115
*   题目: 35.Search Insert Position
*   网址:https://oj.leetcode.com/problems/search-insert-position/
*   结果:AC
*   来源:LeetCode
*   博客:
**********************************/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int searchInsert(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 - start) >> 1);
            // 目标找到
            if(A[mid] == target){
                return mid;
            }//if
            // 目标在左半部分
            else if(A[mid] > target){
                end = mid - 1;
            }//else
            // 目标在右半部分
            else{
                start = mid + 1;
            }//else
        }//while
        // 目标元素没有找到则找插入位置
        return start;// end + 1
    }
};

int main(){
    Solution solution;
    int A[] = {1,3,5,6};
    int n = 4;
    int target = 0;
    int result = solution.searchInsert(A,n,target);
    // 输出
    cout<<result<<endl;
    return 0;
}

8.【输入一个排好序的数组的一个旋转,输出旋转数组的最小元素

【题目】

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。

【分析】

具体参考:[经典面试题]输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。

【代码】
/*********************************
*   日期:2015-01-04
*   作者:SJF0115
*   题目: 输入一个排好序的数组的一个旋转,输出旋转数组的最小元素
*   博客:
**********************************/
#include <iostream>
using namespace std;

int SearchMin(int A[],int n){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 数组有序
    if(A[end] > A[start]){
        return A[start];
    }//if
    // 数组旋转
    // 二分查找
    while(start <= end){
        int mid = (start + end) / 2;
        // [start,mid]有序[mid,end]无序
        if(A[mid] > A[start]){
            start = mid;
        }
        // [start,mid]无序[mid,end]有序
        else if(A[mid] < A[start]){
            end = mid;
        }
        else{
            return A[mid+1];
        }
    }//while
}

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


9.【输入一个排好序的数组的一个旋转,求target在数组中下标,没有重复元素

/*********************************
*   日期:2014-01-15
*   作者:SJF0115
*   题号: 33.Search in Rotated Sorted Array
*   来源:http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;

class Solution {
public:
    //二分查找
    int search(int A[], int n, int target) {
        int start = 0,end = n-1;
        int mid;
        while(start <= end){
            mid = (start + end) / 2;
            if(A[mid] == target){
                return mid;
            }
            //中间元素大于最左边元素则左部分为有序数组
            else if(A[mid] >= A[start]){
                //目标位于左部分
                if(target >= A[start] && target <= A[mid]){
                    end = mid - 1;
                }
                //目标位于右部分
                else{
                    start = mid + 1;
                }
            }
            //中间元素小于最右边元素则右部分为有序数组
            else{
                //目标位于左部分
                if(target <= A[end] && target >= A[mid]){
                    start = mid + 1;
                }
                //目标位于左部分
                else{
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
};
int main() {
    int result;
    Solution solution;
    int A[] = {3,1};
    result = solution.search(A,2,1);
    printf("Result:%d\n",result);
    return 0;
}




10.【Find Minimum in Rotated Sorted Array]

[LeetCode]153.Find Minimum in Rotated Sorted Array

11.【Find Minimum in Rotated Sorted Array II ]

[LeetCode]154.Find Minimum in Rotated Sorted Array II


分享到:
评论

相关推荐

    嵌入式经典面试题嵌入式经典面试题

    嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题

    Python经典面试题-总结

    Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 ...

    C ++经典面试题,C ++经典面试题

    C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题

    10万字208道Java经典面试题总结(附答案).pdf

    10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附...

    java经典面试题

    面试时整理的资料,大家可以看看,面试的java题目,面试时整理的资料,大家可以看看,面试的java题目

    PHP经典面试题

    PHP经典面试题 PHP经典面试题 PHP经典面试题 PHP经典面试题 PHP经典面试题

    SQL经典面试题及答案SQL经典面试题及答案

    SQL经典面试题及答案 SQL经典面试题及答案

    vue经典面试题及答案.rar

    vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典...

    2022年SQL数据库经典面试题笔试题 (2).pdf

    2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022...

    java经典面试题(典藏版)

    java经典面试题(典藏版)java经典面试题(典藏版)java经典面试题(典藏版)java经典面试题(典藏版)java经典面试题(典藏版)

    cobol面试题 经典面试题

    cobol面试题 cobol面试题 cobol面试题

    各公司经典面试题选取

    各公司经典面试题选取

    Spring经典面试题

    Spring经典面试题Spring经典面试题Spring经典面试题Spring经典面试题

    c语言经典面试题

    c语音经典面试题,来自培训机构内部面试题库。

    Redis面试题汇总经典.docx

    Redis面试题汇总经典.docxRedis面试题汇总经典.docxRedis面试题汇总经典.docxRedis面试题汇总经典.docxRedis面试题汇总经典.docxRedis面试题汇总经典.docxRedis面试题汇总经典.docxRedis面试题汇总经典.docxRedis...

    sqlserver 经典面试题

    sqlserver 经典面试题。详细说明面试重点,值得参考

    IT行业经典面试题,121套面试题

    IT行业经典面试题,121套面试题 IT行业经典面试题,121套面试题 IT行业经典面试题,121套面试题 IT行业经典面试题,121套面试题

    华为经典面试题系列二

    华为经典面试题系列二,华为经典面试题系列二

    sql经典面试题

    sql经典面试题 mysql 很好的面试题 sql经典面试题 mysql 很好的面试题 sql经典面试题 mysql 很好的面试题 sql经典面试题 mysql 很好的面试题 sql经典面试题 mysql 很好的面试题 sql经典面试题 mysql 很好的面试题 ...

    javascript的经典面试题汇总

    javascript面试题汇总javascript面试题汇总javascript面试题汇总

Global site tag (gtag.js) - Google Analytics