# 排序搜索，计数数量小于目标值

``````/**
* Implement function countNumbers that accepts a sorted array of unique integers and,
* efficiently with respect to time used, counts the number of array elements that are less than the parameter lessThan.
* <p>
* For example, SortedSearch.countNumbers(new int[] { 1, 3, 5, 7 }, 4)
* should return 2 because there are two array elements less than 4.
*/
``````

`````` public static int countNumbers(int[] sortedArray, int lessThan) {
int count = 0;
if(sortedArray == null) {
return 0;
}
List<Integer> numbers  = new ArrayList<>();
for (int i = 0; i < sortedArray.length; i++) {
if (sortedArray[i] < lessThan) {
count++;
} else  {
break;
}
}
return count;
}
``````

sortedArray包含lessThan时的

Harshal Parekh：

``````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 - start) / 2;
if (sortedArray[mid] < lessThan) {
if (mid < sortedArray.length - 1 && sortedArray[mid + 1] < lessThan) {
start = mid + 1;
continue;
} else {
return mid + 1;
}
}

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

``````Arrays.binarySearch(new int[]{1, 2, 4}, 3) + 1) * -1;
``````

0 条评论