Loading...
Loading...
Loading...
A class teacher keeps the test marks of n students in a list sorted from low to high. Some marks repeat.
A late student scores x. The teacher wants to insert x into the list and keep it sorted. If x equals marks already in the list, x goes before all of them. Print the index where x goes, counting from 0.
Example 1
Input
5 60 35 48 60 60 92
Output
2
35 and 48 are smaller than 60, so x goes at index 2, before both 60s.
Example 2
Input
4 100 10 20 30 40
Output
4
x is larger than every mark, so it goes at the end, index 4.
Try the problem first. Open one hint at a time.
The answer is the number of marks that are strictly smaller than x.
Because the list is sorted, all smaller marks come first. Look for the first mark that is at least x.
Let the answer range be 0 to n (not n - 1), because x may go after every mark.
If the middle mark is smaller than x, the answer is to its right. Otherwise the middle itself may be the answer, so keep it.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor