LeetCode-Search for a Range

LeetCode-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].

解題分析：就是一個二分搜索的應用，不難。但是就是注意一個數組越界的檢查。LeetCode自己的編譯器會報錯。

int a,b;
 a=num;
 b=num;

while(A[a] == target )  a--;
while(A[b] == target )  b++;

最後做了一個數組的溢出判斷，終於AC了

int a,b;
        a=num;
        b=num;
        while(A[a] == target && a >= 0)  a--;
        while(A[b] == target && b <= n-1)  b++;

class Solution {
private: int binary_search(int* a, int len, int goal)
    {
    int low = 0;
    int high = len - 1;
    while(low <= high)
    {
        int middle = (low + high)/2;
        if(a[middle] == goal)
            return middle;
        else if(a[middle] > goal)
            high = middle - 1;
        else
            low = middle + 1;
    }
    return -1;
    }

public:
    vector searchRange(int A[], int n, int target) {
        vector s;
        int num = binary_search(A,n,target);
        if(num == -1) {s.push_back(-1);s.push_back(-1);}
        else {
        int a,b;
        a=num;
        b=num;
        while(A[a] == target && a >= 0)  a--;
        while(A[b] == target && b <= n-1)  b++;
        s.push_back((++a));
        s.push_back((--b));
        }
        return s;
    }
};