[LeetCode]34.Search for a Range

【题目】

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

【分析】

这是一种二分查找的变形，利用两次二分查找就可以实现，第一次是找到目标元素的连续最小位置，第二次是找到目标元素的连续最大位置。

所以算法的时间复杂度仍是O(logn)，空间复杂度是O(1)

具体可以参考：  [经典面试题]二分查找问题汇总

【代码】

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

【代码二】

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){
                start = mid + 1;
            }
            // 目标位于左半部分
            else{
                end = mid - 1;
            }
        }//while
        // 目标不存在的情况
        // 此时start = end
        if(A[start] != target){
            return -1;
        }//if
        else{
            return start;
        }
    }
    // 目标元素的最大位置
    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){
                end = mid - 1;
            }//
            // 目标位于左半部分
            else{
                start = mid + 1;
            }
        }//while
        // 目标不存在的情况
        // 此时start = end
        if(A[end] != target){
            return -1;
        }//if
        else{
            return end;
        }
    }
};