Find First and Last Position of Element in Sorted Array Solutions in C++

// Source : https://oj.leetcode.com/problems/search-for-a-range/
// Author : Hao Chen
// Date   : 2014-06-26



#include <iostream>
#include <vector>
using namespace std;

int binary_search(int A[], int low, int high, int key);

/*
 *   O(log n) solution must be something like binary search.
 *
 *   So, we can use the binary search to find the one postion - `pos`
 *   
 *   then, we can keep using the binary search find the target in A[0..pos-1] and A[pos+1..n]
 *
 *   The code below is self-explaination
 */
vector<int> searchRange(int A[], int n, int target) {
    int pos = binary_search(A, 0, n-1, target);

    vector<int> v;
    int low = -1, high = -1;
    if (pos >=0){
        low = high = pos;
        int l = low;
        do {
            low = l;
            l = binary_search(A, 0, low - 1, target);
        }while (l>=0);

        int h = high;
        do {
            high = h;
            h = binary_search(A, high + 1, n-1, target);
        }while (h>=0);
    }

    v.push_back(low);
    v.push_back(high);
    return v;

}

int binary_search(int A[], int low, int high, int key){

    while (low<=high) {
        int mid = low + (high-low)/2;
        if (A[mid] == key) {
            return mid;
        }
        if (key > A[mid]) {
            low = mid + 1;
        }
        if (key < A[mid]) {
            high = mid - 1;
        }
    }
    return -1;
}

void printVector( vector<int>&  pt)
{
    cout << "{ ";
    for(int j=0; j<pt.size(); j++){
        cout << pt[j] << " ";
    }
    cout << "} " << endl;
}


int main()
{
    const int cnt=6;
    int a[cnt] ={5, 7, 7, 8, 8, 10};

    vector<int> v;
    v = searchRange(a, cnt, 8);     
    printVector(v);    


    int b[cnt] ={5, 5, 5, 8, 8, 10};
    v = searchRange(b, cnt, 5);     
    printVector(v);    

    int c[cnt] ={5, 5, 5, 5, 5, 5};
    v = searchRange(c, cnt, 5);     
    printVector(v);    
    return 0;
}

#include <vector>

using std::vector;

class Solution {
    int binarySearch(int A[], int l, int r, int target) {
        for (int mid; l <= r; ) {
            mid = ( l + r ) >> 1;
            if      ( A[mid] < target ) l = mid + 1;
            else if ( A[mid] > target ) r = mid - 1;
            else return mid;
        }
        return -1;
    }
public:
    vector<int> searchRange(int A[], int n, int target) {
        int iPos = binarySearch( A, 0, n-1, target ), l = -1, r = -1;
        if ( iPos != -1 ) {
            l = r = iPos;
            for (int lo = l; (lo = binarySearch(A, 0,   lo-1, target)) != -1; l = lo ) ;
            for (int hi = r; (hi = binarySearch(A, hi+1, n-1, target)) != -1; r = hi ) ;
        }
        return {l ,r};
    }
};

/// Source : https://leetcode.com/problems/search-for-a-range/description/
/// Author : liuyubobobo
/// Time   : 2017-11-16

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Linear Scan
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        int first = nums.size() + 1, last = -1;
        for(int i = 0 ; i < nums.size() ; i ++)
            if(nums[i] == target){
                first = min(first, i);
                last = max(last, i);
            }

        int res[2] = {first, last};
        if(first == nums.size() + 1){
            assert(last == -1);
            res[0] = res[1] = -1;
        }

        return vector<int>(res, res + 2);
    }
};


void printVec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    int nums[6] = {5, 7, 7, 8, 8, 10};
    int target = 8;
    vector<int> vec(nums, nums + sizeof(nums) / sizeof(int));

    printVec(Solution().searchRange(vec, target));

    return 0;
}

/// Source : https://leetcode.com/problems/search-for-a-range/description/
/// Author : liuyubobobo
/// Time   : 2017-11-16

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

/// Using STL lower_bounf and upper_bound
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        vector<int>::iterator lowerIter = lower_bound(nums.begin(), nums.end(), target);
        int first = -1;
        if(lowerIter != nums.end() && *lowerIter == target)
            first = lowerIter - nums.begin();

        vector<int>::iterator upperIter = upper_bound(nums.begin(), nums.end(), target);
        int last = -1;
        if(upperIter == nums.end() && nums.size() > 0 && nums.back() == target)
            last = nums.size() - 1;
        else if(upperIter != nums.end() && *(upperIter - 1) == target)
            last = upperIter - nums.begin() - 1;

        if(first == -1)
            assert(last == -1);

        int res[2] = {first, last};
        return vector<int>(res, res + 2);
    }
};


void printVec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    int nums1[6] = {5, 7, 7, 8, 8, 10};
    int target1 = 8;
    vector<int> vec1(nums1, nums1 + sizeof(nums1) / sizeof(int));

    printVec(Solution().searchRange(vec1, target1));
    // 3, 4

    // ---

    int nums2[1] = {1};
    int target2 = 0;
    vector<int> vec2(nums2, nums2 + sizeof(nums2) / sizeof(int));

    printVec(Solution().searchRange(vec2, target2));
    // -1, -1

    // ---

    int nums3[1] = {1};
    int target3 = 1;
    vector<int> vec3(nums3, nums3 + sizeof(nums3) / sizeof(int));

    printVec(Solution().searchRange(vec3, target3));
    // 0, 0

    // ---
    vector<int> vec4;
    printVec(Solution().searchRange(vec4, 0));
    // -1, -1

    return 0;
}

/// Source : https://leetcode.com/problems/search-for-a-range/description/
/// Author : liuyubobobo
/// Time   : 2017-11-16

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Binary Search
/// Time Complexity: O(logn)
/// Space Complexity: O(1)
class Solution {

public:
    vector<int> searchRange(vector<int>& nums, int target) {

        int lowerIndex = firstOccurance(nums, target);
        int first = -1;
        if(lowerIndex != nums.size() && nums[lowerIndex] == target)
            first = lowerIndex;
        // cout << "first = " << first << endl;

        int upperIndex = lastOccurance(nums, target);
        int last = -1;
        if(upperIndex == nums.size() && nums.size() > 0 && nums.back() == target)
            last = nums.size() - 1;
        else if(upperIndex != nums.size() && nums[upperIndex - 1] == target)
            last = upperIndex - 1;
        // cout << "last = " << last << endl;

        int res[2] = {first, last};
        return vector<int>(res, res + 2);
    }

private:
    // same to lower_bound
    int firstOccurance(const vector<int>& nums, int target){

        int l = 0, r = nums.size();
        while(l != r){
            int mid = l + (r - l) / 2;
            if(nums[mid] < target)
                l = mid + 1;
            else    // nums[mid] >= target
                r = mid;
        }
        return l;
    }

    // same to upper_bound
    int lastOccurance(const vector<int>& nums, int target){

        int l = 0, r = nums.size();
        while(l != r){
            int mid = l + (r - l) / 2;
            if(nums[mid] <= target)
                l = mid + 1;
            else    // nums[mid] > target
                r = mid;
        }
        return l;
    }
};


void printVec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    int nums1[6] = {5, 7, 7, 8, 8, 10};
    int target1 = 8;
    vector<int> vec1(nums1, nums1 + sizeof(nums1) / sizeof(int));

    printVec(Solution().searchRange(vec1, target1));
    // 3, 4

    // ---

    int nums2[1] = {1};
    int target2 = 0;
    vector<int> vec2(nums2, nums2 + sizeof(nums2) / sizeof(int));

    printVec(Solution().searchRange(vec2, target2));
    // -1, -1

    // ---

    int nums3[1] = {1};
    int target3 = 1;
    vector<int> vec3(nums3, nums3 + sizeof(nums3) / sizeof(int));

    printVec(Solution().searchRange(vec3, target3));
    // 0, 0

    // ---
    vector<int> vec4;
    printVec(Solution().searchRange(vec4, 0));
    // -1, -1

    return 0;
}