Is it possible to use binary search to find the last occurrence of an element in an array?

Question

Given an array of n elements, ordered in non-decreasing order, find the first and last occurrence of a number in an array. Since the array is sorted, the use of binary search is suggested. I used it to find the first entry, but I do not know how to change it to search for the last entry.

Alex Chermenin Alex Chermenin 4,987 9 31 · Accepted Answer · 2017-10-20T14:06:38

Just use different behaviors when deciding which way to go, if you find a value equal to the desired. Java example:

int binarySearch(int[] a, int fromIndex, int toIndex, int key, boolean last) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key || (last && midVal == key)) low = mid + 1; else if (midVal > key || (!last && midVal == key)) high = mid - 1; } return last ? high : low; }

@Alex Chermenin, do I understand correctly that fromIndex should be 0, and toIndex len (a) -1?
@ZvyagintsevDenis To bypass the entire array: fromIndex is 0, toIndex is equal to the length of the array.
The code already has a decrease by one for the variable high.
@AlexChermenin And is checking for the existence of an element in an array to slow down the work of the algorithm?
You can not add a test for existence, simply if as a result, the index of the last entry was less than the index of the first - then there is no such element, and by indexes you can determine where to insert it so that the sorting does not get lost :)

Answer 2 · 2017-10-20T13:59:11

If your array is sorted (and this is a mandatory condition for binary search), then the same values are next to each other. Binary search you will find some of them (not necessarily the first or last), then you need to find the boundaries of the subarray (where the desired value borders on more or less), for which you can also use the binary search (so as not to look for brute force).

And if an array of a million elements and there are such numbers - half a million
Then it is necessary in both directions to look for the first non-coinciding element on the principle of binary search.

KoVadim KoVadim 85.4k four 66 126 · Answer 3 · 2017-10-20T14:10:00

Use binary search, just look not for the number itself, but for the number + - epsilon, where epsilon is some small positive number, less difference between two different numbers is guaranteed. If this is an array of integers - epsilon can be equal to 0.5. Yes, you just need to understand that we will not find the numbers in this case, but the border is yes. This algorithm can be "slightly accelerated" if the upper limit is sought not from the beginning to the end, but from the lower limit to the end.

In Java, I don’t know, but with their hands they differ exactly in 1 character (where <= or <).
Yes, I thought about lower_bound and upper_bound, but judging by the question they want a general algorithm.
Here's another floating point is not enough, if the array of integers ...

Alex Titov Alex Titov 745 one 6 · Answer 4 · 2017-10-20T14:24:53

If c ++, the std::equal_range does what is required.

Answer 5 · 2017-10-20T14:29:25

In python, this is generally implemented in two lines:

 lower_bound = my_list.index(10) upper_bound = len(my_list) - list(reversed(my_list)).index(10) - 1

More optimal option:

 lower_bound = my_list.index(10) for k in range(lower_bound+1, len(my_list)+1): if my_list[k] != 10: break upper_bound = k - 1

number of repetitions: 10 000 000
list of 30 items

 первый вариант: 16.31380480196094 второй вариант: 10.351039482047781

.len , .index - O (1), .len - O (1), reversed - O (N).
@YaroslavSurzhikov in Java is also possible in a single line IntStream.range(0, array.length).reduce(-1, (l, r) -> array[r] == key ? r : l);
@YaroslavSurzhikov, and exception handling (ValueError) slows down the algorithm?

Is it possible to use binary search to find the last occurrence of an element in an array?

5 answers 5

More articles: