the problem is to return the lowest index of the element on a sorted list with duplicates. but my code is giving segmentation error.I am not able to identify the error in code.

int binary_search(const vector<int> &a, int left, int right, int x)
{
    // write your code here
    if (right - left == 0)
        return right;
    while (right >= left)
    {
        int mid = right - left / 2;
        if (a[mid] == x)
            return binary_search(a, left, mid, x);
        else if (a[mid] > x)
            right = mid - 1;
        else
            left = mid   1;
    }
    return -1;
}

int main()
{
    int n;
    std::cin >> n;
    vector<int> a(n);
    for (size_t i = 0; i < a.size(); i  )
    {
        std::cin >> a[i];
    }
    int m;
    std::cin >> m;
    vector<int> b(m);
    for (int i = 0; i < m;   i)
    {
        std::cin >> b[i];
    }
    for (int i = 0; i < m;   i)
    {
        // replace with the call to binary_search when implemented
        std::cout << binary_search(a, 0, (int)a.size() - 1, b[i]) << ' ';
    }
}

CodePudding user response：

When you find the result a[mid] == x, store it & keep searching to the left portion for the lowest index.

int binary_search(const vector<int> &a, int left, int right, int x)
{
    // write your code here
    if (right - left == 0)
        return right;
    int idx = -1;

    while (right >= left)
    {
        int mid = right - left / 2;
        // modified
        if (a[mid] == x) {
            idx = mid;
            right = mid - 1;
        }
        else if (a[mid] > x)
            right = mid - 1;
        else
            left = mid   1;
    }
    return idx;
}

P.S: You might want to check the way you're calculating mid value! Usually, mid = (left right) / 2 or mid = left (right - left) / 2 to avoid overflow.