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

[算法]二分查找算法

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在数组中下标，没有重复元素】

具体参考：[LeetCode]33.Search in Rotated Sorted Array

/*********************************
*   日期：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