SortedSearch.countNumbers（new int [] {1,3,5,7}，4）应返回2，因为有两个数组元素小于4

Question

需要更有效的方式

以下是结果：

• 示例案例：正确答案
• 各种小阵列：正确答案
• sortedArray包含lessThan：超出时间限制时的性能测试
• sortedArray不包含lessThan时的性能测试：超出时间限制

以下是代码：

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));
    }
}

参考链接：Try here

Answer 1

没有必要排序，只有foreach，这是更有效的方法

Answer 2

试试下面的代码

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;

}

Answer 3

@shmosel代码是正确的，但不需要for循环。 binarySearch方法返回您要查找的值的索引。因此，你只需要归还我。

public static int countNumbers(int[] sortedArray, int lessThan) {
    int i = java.util.Arrays.binarySearch(sortedArray, lessThan);
    if (i < 0) 
        return -i - 1;
    else
        return i;
}

Answer 4

您可以使用Java的内置二进制搜索：

public static int countNumbers(int[] sortedArray, int lessThan) {
    int i = java.util.Arrays.binarySearch(sortedArray, lessThan);
    if (i < 0) {
        return -i - 1;
    } else {
        // in case of duplicates, find first occurrence
        for (; i > 0 && sortedArray[i - 1] == lessThan; i--);
        return i;
    }
}

Answer 5

他们希望你使用Array.BinarySearch方法获得100％。

using System;

public class SortedSearch
    {
    public static int CountNumbers(int[] sortedArray, int lessThan)
    {
        if (sortedArray[0] >= lessThan) return 0;

        int lengthOfArray = sortedArray.Length;
        if (lengthOfArray == 0) return 0;
        if (sortedArray[lengthOfArray - 1] < lessThan) return lengthOfArray;

        int index = Array.BinarySearch(sortedArray, lessThan);
        if (index < 0)
            return ~index;

        return index;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4));
    }
}