Miljan Rakita Miljan Rakita - 2 days ago 5
Java Question

My binary search code is too slow

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:


  1. What can i do to improve my algorithm efficiency.

  2. 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].


Three Cases to Consider

There are three cases to consider:

  1. x does not occur in the array
  2. x occurs in the array exactly once
  3. x occurs in the array more than once

How To Solve

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.

Comments