0

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

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

You must write an algorithm with O(log n) runtime complexity.

I wrote this code in leetcode but it has only passed 67 test cases out of 88.Can someone please tell me the problem with this code.

class Solution {
public:
int FirstOccurence(vector<int> arr, int n, int x) {
    int low = 0, high = n - 1;
    int ans = -1;

    while (low <= high) {
        int mid = (low + high) / 2;
        // maybe an answer
        if (arr[mid] == x) {
            ans=mid;
            high=mid-1;
    }
    else if (arr[mid]< x) {
            low=mid+1;
    }
    else high=mid-1;
    }
    return ans;
}

int LastOccurence(vector<int> arr, int n, int x) {
    int low = 0, high = n - 1;
    int ans = -1;

    while (low <= high) {
        int mid = (low + high) / 2;
        // maybe an answer
        if (arr[mid]== x) {
            ans = mid;
            //look for smaller index on the left
            low=mid+1;
        }
        else if(arr[mid]>x){
            high=mid-1;
        }
        else {
            low = mid + 1; // look on the right
        }
    }
    return ans;
}
    vector<int> searchRange(vector<int>& nums, int target) {
        int n=nums.size()-1;
        int k=target;
        int a=FirstOccurence(nums,n,k);
    int b=LastOccurence(nums,n,k);
    return{a,b};
    }
};
Raghav Khandelwal
  • 11
  • 2
  • 2
    As far as I know, Leetcode is on the better side of the so-called "competition" or "judge" sites, because it gives you the failed test-case. You can take that test-case, hard-code it into a [mre], and then [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your code locally on your own system. – Some programmer dude Jul 31 '23 at 05:57
  • 1
    The `n` argument is the largest valid index, and `high` is one less than that, so you can never look at the last element. (Get used to the conventional half-open intervals and stick to them.) – molbdnilo Jul 31 '23 at 06:30
  • *Can someone please tell me the problem with this code.* -- [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). – PaulMcKenzie Jul 31 '23 at 06:41
  • FYI -- you don't need to write any binary search function to solve this problem. The [std:::lower_bound/upper_bound](https://en.cppreference.com/w/cpp/algorithm/lower_bound) functions already do the search and will return iterators to either the target element, or to the element before/after the target, or `nums.end()` if the target isn't in `nums`. From there, it is some simple logic to clean things up and return the `std::distance` to the iterators. – PaulMcKenzie Jul 31 '23 at 07:30
  • `int mid = (low + high) / 2;` -- `low + high` will cause an overflow if there are many elements. – PaulMcKenzie Jul 31 '23 at 07:33
  • [Quick and dirty solution](https://godbolt.org/z/KcoTrPz7j). Note the usage of `std::lower_bound` and `std::upper_bound`. If you're going to use Leetcode, know your algorithm functions such as `std::lower_bound/upper_bound` so that the questions can be easily answered (instead of writing (buggy) code from scratch). – PaulMcKenzie Jul 31 '23 at 07:53
  • @PaulMcKenzie I added an opition using `std::equal_range` to the answer. – Ted Lyngmo Jul 31 '23 at 07:54
  • 1
    @TedLyngmo -- Yes, that is even better than my solution. The bottom line is to know how to utilize C++ in answering the Leetcode questions efficiently, which the OP was not doing. – PaulMcKenzie Jul 31 '23 at 08:01
  • Consider posting here: https://codegolf.stackexchange.com/ – ryanwebjackson Jul 31 '23 at 21:05

1 Answers1

1

You are sending in nums.size() - 1 to the binary search functions and inside them you make high = n - 1, effectively making high = nums.size() - 2 so all tests where the target is the greatest number in the vector will fail.

An easy fix would be to not send in n at all. You already send in the vector and can call .size() inside the functions:

int FirstOccurence(const std::vector<int>& arr, int x) {  // no `n`
    int low = 0, high = static_cast<int>(arr.size()) - 1; // size() - 1 instead

int LastOccurence(const std::vector<int>& arr, int x) {   // no `n`
    int low = 0, high = static_cast<int>(arr.size()) - 1; // size() - 1 instead

Then at the call site:

std::vector<int> searchRange(const std::vector<int>& nums, int target) {
    int k = target;
    int a = FirstOccurence(nums, k); // no `n`
    int b = LastOccurence(nums, k);  // no `n`
    return {a, b};
}

An alternative could be to use std::equal_range from the standard library:

#include <algorithm> // equal_range
#include <iterator>  // distance

std::vector<int> searchRange(const std::vector<int>& nums, int target) {
    std::vector<int> res{-1, -1};
    auto [fit, lit] = std::equal_range(nums.begin(), nums.end(), target);

    if (fit != lit) {
        res[0] = static_cast<int>(std::distance(nums.begin(), fit));
        res[1] = static_cast<int>(std::distance(nums.begin(), lit)) - 1;
    }
    return res;
}
Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108