CODEWITHSUNDEEP
c++binary-search
Raghav Khandelwal
Raghav Khandelwal

Reputation: 11

Failing a test Case in finding the first and last position of element using binary search

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};
    }
};

Upvotes: 0

Views: 110

Answers (1)

Ted Lyngmo
Ted Lyngmo

Reputation: 117832

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;
}

Upvotes: 1

Related Questions