Miljan Rakita - 3 months ago 23

Java Question

i am trying to solve this algorithm task. And when i submit my code, on some test cases my code is too slow and on some my code gives wrong output. I was trying to find where i made mistake but i really couldnt. Because in test cases where my code fails there are more thousand length arrays and i cant check every output to find mistake.

So i was wondering if you could give me some advice:

- What can i do to improve my algorithm efficiency.
- Where i make mistake so on some test cases i get wrong output.

Here is my code:

`public class Main`

{

public static void main(String[] args)

{

Scanner sc = new Scanner(System.in);

int length = sc.nextInt();

int arr[] = new int[length];

for(int i=0; i<length; i++)

arr[i] = sc.nextInt();

int test = sc.nextInt();

int type, check;

for(int i=0; i<test; i++)

{

type = sc.nextInt();

check = sc.nextInt();

if(type == 0)

{

System.out.println(greaterOrEqualThan(arr, check, length));

}

else if(type == 1)

{

System.out.println(greaterThan(arr, check, length));

}

}

}

public static int greaterThan(int arr[],int x, int length)

{

int low = 0;

int high = length-1;

int mid;

while( low+1 < high)

{

mid = (high+low)/2;

if(arr[mid] <= x)

low = mid;

else if(arr[mid] > x)

high = mid;

}

int startIndex;

if(arr[low] > x && arr[low] != arr[high])

startIndex = low;

else if(arr[high] > x && arr[high] != arr[low])

startIndex = high;

else

return 0;

return length-startIndex;

}

public static int greaterOrEqualThan(int arr[], int x, int length)

{

int low = 0;

int high = length-1;

int mid;

while(low+1 < high)

{

mid = (low+high)/2;

if(arr[mid] < x)

low = mid;

else if(arr[mid] == x)

{

high = mid;

break;

}

else

high = mid;

}

int startIndex;

if(arr[low] >= x)

startIndex = low;

else if(arr[high] >= x)

startIndex = high;

else

return 0;

return length-(startIndex);

}

}

Answer

I think one or both of your algorithms may be incorrect in cases where there are multiple instances of the target value in the array. (e.g. `[1,3,3,3,5]`

.

There are three cases to consider:

`x`

does not occur in the array`x`

occurs in the array exactly once`x`

occurs in the array more than once

I recommend using a classical binary search algorithm for each of the two methods (the exact binary search algorithm without modification). What you do after that is what is different.

So first, run a classical binary search algorithm, inlined directly into your methods (so that you have access to the terminal values of `low`

and `high`

).

Second, after the binary search terminates, test if `array[mid] != x`

. If `array[mid] != x`

, then `x`

does not occur in the array and it is true that `low == high + 1`

(since `high`

and `low`

have crossed. Therefore, the count of numbers in the array which are not less than `x`

and the count of numbers in the array which are greater than `x`

are both equal to `array.length() - low`

.

Third, if it is instead true that `array[mid] == x`

, then `x`

does occur one or more times in the array. Since the classical binary search algorithm terminates immediately when if finds `x`

, it is indeterminate "which" `x`

it terminated on.

In this case, in order to find the count of numbers not less than `x`

, you must find the "first" `x`

in the array using the following code snippet:

```
do {
mid = mid - 1;
} while (array[mid] == x);
```

`mid`

will then be the index of the element immediately *before* the "first" `x`

in the array, and so the count of numbers not less than `x`

will be `array.length() - mid + 1`

.

Similarly, in order to find the count of numbers greater than `x`

, you must first find the "last" `x`

in the array using the following code snippet:

```
do {
mid = mid + 1;
} while (array[mid] == x);
```

`mid`

will then be the index of the element immediately *after* the "last" `x`

in the array, and so the count of numbers greater than `x`

will be `array.length() - mid - 1`

.