java - SortedSearch.countNumbers(new int[] { 1, 3, 5, 7 }, 4) should return 2 because there are two array elements less than 4

Question

Need more efficient way

Following are the results:

• Example case: Correct answer

• Various small arrays: Correct answer

• Performance test when sortedArray contains lessThan: Time limit exceeded

• Performance test when sortedArray doesn't contain lessThan: Time limit exceeded

Following is the code:

import java.util.Arrays;

public class SortedSearch {
    public static int countNumbers(int[] sortedArray, int lessThan) {

        Arrays.sort(sortedArray);
        int count =0;

        for(int num :sortedArray){

            if(num < lessThan)
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(SortedSearch.countNumbers(new int[] { 1, 3, 5, 7 }, 4));
    }
}

Ref Link : Try here

Answer 1

Try below code

public static int countNumbers(int[] sortedArray, int lessThan) {
    int start = 0;
    int end = sortedArray.length - 1;
    int mid = 0;
    while (start <= end) {
        mid = (start + end) / 2;
        if (sortedArray[mid] < lessThan) {
            if (mid < sortedArray.length - 1 && sortedArray[mid + 1] < lessThan) { // check id next value is also valid
                start = mid + 1;
                continue;
            } else
                return mid + 1;
        }

        if (sortedArray[mid] >= lessThan) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return 0;

}