gpt4 book ai didi

java - 使用二分查找高效地获取排序数组中小于给定数字的数字计数

转载 作者:行者123 更新时间:2023-12-01 19:13:52 26 4
gpt4 key购买 nike

我的问题陈述是这样的 -查找排序数组中小于给定数字的数字的计数,这应该在时间上有效地完成。我编写了一个使用二分搜索的程序来获取计数,但从时间复杂度角度来看它失败了。需要帮助来实现这一目标。

import java.util.Arrays;

public class SortedSearch {
public static int countNumbers(int[] sortedArray, int lessThan) {
if(sortedArray.length ==1 || sortedArray.length == 0) {
return singleElement(sortedArray, lessThan);
}
else {
return binarySearch(sortedArray, lessThan);
}
}

public static int singleElement(int[] sortedArray, int searchVal) {
if(sortedArray.length == 0) {
return 0;
}
if(sortedArray[0] < searchVal) {
return 1;
}
return 0;
}

private static int binarySearch(int[] sortedArray, int searchVal) {
int low = 0;
int high = (sortedArray.length)-1;
int mid = (low + high)/2;
if((sortedArray.length == 0) || (sortedArray[0] > searchVal)) {
return 0;
}
if(sortedArray[high] < searchVal) {
return sortedArray.length;
}
if(sortedArray[high] == searchVal) {
return sortedArray.length-1;
}
if(sortedArray[mid] < searchVal) {
int newLow = low;
int newHigh = calculateNewHigh(sortedArray, newLow, 0, searchVal);
int[] newArray = Arrays.copyOfRange(sortedArray, newLow, newHigh+1);
return newArray.length;
}
else {
int newLow = low;
int newHigh = mid;
int[] newArray = Arrays.copyOfRange(sortedArray, newLow, newHigh+1);
return binarySearch(newArray, searchVal);
}
}

private static int calculateNewHigh(int[] sortedArray, int low, int previousHigh, int searchVal) {
int newHigh = previousHigh + (sortedArray.length-low)/2;
if(sortedArray[newHigh] < searchVal) {
newHigh = calculateNewHigh(sortedArray, newHigh, newHigh, searchVal);
}
if(sortedArray[newHigh] == searchVal) {
newHigh--;
}
if(sortedArray[newHigh] > searchVal) {
newHigh--;
}
return newHigh;
}

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

最佳答案

既然你无论如何都在使用Arrays,那就不要使用Arrays.binarySearch(int[] a, int key)方法,而不是尝试编写自己的方法?

public static int countNumbers(int[] sortedArray, int lessThan) {
int idx = Arrays.binarySearch(sortedArray, lessThan);
if (idx < 0)
return -idx - 1; // insertion point
while (idx > 0 && sortedArray[idx - 1] == lessThan)
idx--;
return idx; // index of first element with given value
}

while循环1是必要的,因为javadoc说:

If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

1) 如果例如,此循环不是最佳循环所有值都相同,请参见例如Finding multiple entries with binary search

关于java - 使用二分查找高效地获取排序数组中小于给定数字的数字计数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59441449/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com