Click here to Skip to main content
15,888,610 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Question is to find the first and the last index of any number in a sorted array. (repetition of numbers is allowed?

Below is my logic for that program. Can anyone tell me why it is showing TIME LIMIT EXCEEDED?
And if logic is incorrect then what is to be corrected.


What I have tried:

import java.io.*;

import java.util.*;



public class Main{



public static void main(String[] args) throws Exception {

Scanner scn = new Scanner(System.in);

int n = scn.nextInt();

int a[] = new int[n];

for(int i=0;i<a.length;i++){

a[i] = scn.nextInt();

}

int l = 0;

int h = a.length - 1;

int x = scn.nextInt();

int first_index = 0;
int last_index = 0;
int mid = 0;

while(l <= h){

mid = (l+h)/2;

if( x < a[mid])
{

h = mid - 1;

}
else if(x > a[mid])
{

l = mid + 1;

}

else
{

first_index = mid;

last_index = mid;

}

}

int i = mid;

int j = mid;

if(a[first_index] == a[first_index-1]){

i--;

first_index--;

}

if(a[last_index] == a[last_index+1]){

j++;

last_index++;

}

first_index = i;

last_index = j;

System.out.println(first_index);

System.out.println(last_index);

}



}
Posted
Updated 17-Sep-21 23:27pm
v2
Comments
Richard MacCutchan 18-Sep-21 5:07am    
Web sites that time your code never tell you why the time limit is exceeded. And since we do not know how they time it, it is difficult to make any suggestions. At a quick glance you could probably search faster using a simple for loop. Once you have found the first index then the last must be beyond that point.

1 solution

Quote:
Can anyone tell me why it is showing TIME LIMIT EXCEEDED?

You problem is that when your dichotomy loop encounter the searched value, the code falls in an infinite loop.
Java
while(l <= h){
    mid = (l+h)/2;
    if( x < a[mid])
    {
        h = mid - 1;
    }
    else if(x > a[mid])
    {
        l = mid + 1;
    }
    else
    {
        first_index = mid;
        last_index = mid;
    }
}

And it is just the first problem in your code.
 
Share this answer
 
Comments
Rishabh Sirohi 18-Sep-21 7:39am    
But how come it is reaching infinite because anyone value(x) will be equal to mid and then last else loop should execute.
Patrice T 18-Sep-21 7:53am    
Did you tested your code ?
Rishabh Sirohi 18-Sep-21 12:10pm    
Yes, it is showing the time limit exceeded.
Patrice T 18-Sep-21 12:15pm    
No, running your code on the site and getting the time limit exceeded is not a test.
If you don't have a java compiler, find an online java ide and run your code on it until you get correct result for input you choose.
Patrice T 18-Sep-21 12:40pm    
Ever heard about debugger ?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900