CODEWITHSUNDEEP
c++
Wolfy
Wolfy

Reputation: 458

Where is the infinite loop occurring?

This problem comes from leetcode:

Given an array of integers nums sorted in ascending order, 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].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Here is my code:

#include <vector>
#include <iostream>

using namespace std;

vector<int> searchRange(vector<int>& nums, int target)
{
    int left = 0;
    int right = (int)nums.size() - 1;
    std::vector<int> result;
    while(left <= right)
    {
        auto mid = (int)(left + right) / 2;
        if(nums[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }

    int next_left = left;
    int next_right = (int) nums.size() - 1;
    while(next_left < next_right)
    {
        auto mid = (int)(left + right + 1) / 2;
        if(nums[mid] > target)
            next_right = mid - 1;
        else
            next_left = mid;
    }

    result = {next_left, next_right};

    return result;


}


int main()
{
    std::vector<int> nums = {1,2,2,2,2,4};
    int target = 2;

    auto result = searchRange(nums, target);
    for(auto it: result)
        std::cout << it << " ";

    return 0;
}

I keep getting a Time Limit Exceeded. I don't know how to fix it any help would be appreciated.

Upvotes: 1

Views: 118

Answers (3)

Duega
Duega

Reputation: 73

To Find Left Index 

    auto mid = (int)(left + right) / 2;

To Find Right Index 

    auto mid = (int)(next_left + next_right + 1) / 2;

I think you should use 

result = {left, next_right};

to return correct result it working with {-1,-1}

Upvotes: 1

R Sahu
R Sahu

Reputation: 206567

A suggestion for tracking down the logic error.

Add couple of lines in the while loops to see how the indices are changing.

while(left <= right)
{
    auto mid = (int)(left + right) / 2;
    if(nums[mid] < target)
        left = mid + 1;
    else
        right = mid;

    // Debugging output.
    std::cout << "left: " << left
              << ", mid: " << mid
              << ", right: " << right << std::endl;
}

and

while(next_left < next_right)
{
    // Incorrect.
    // auto mid = (int)(left + right + 1) / 2;

    auto mid = (int)(next_left + next_right + 1) / 2;
    if(nums[mid] > target)
        next_right = mid - 1;
    else
        next_left = mid;

    // Debugging output.
    std::cout << "next_left: " << next_left
              << ", mid: " << mid
              << ", next_right: " << next_right << std::endl;
}

That should lead you in the right direction.

Upvotes: 2

Sid S
Sid S

Reputation: 6125

In your second loop, this line

auto mid = (int)(left + right + 1) / 2;

should probably be

auto mid = (int)(next_left + next_right + 1) / 2;

Upvotes: 4

Related Questions