[Java] Binary search find first and last occurrence

We saw how to implement binary search both recursively and iteratively, however if the input has duplicates, the result we get is just one possible occurrence of the item.

If we want to find the very first or very last occurrence of the item, we need to tweak the search a bit.

Specifically, we use a temporary variable initialized to -1 and if we find the item in the mid position, we do NOT return yet; instead, we store the matching position in this variable and continue the search as if we hadn't found the element yet.

We do NOT simply walk left or right from there, otherwise we go back to O(N) time.

If we are looking for the first occurrence, we continue the search on the left of the middle, since any prior duplicate must be there. Otherwise we continue on the right, since the last occurrence must be after the current item.

The important part is that at each new step, IF we find the element, we update our temporary result since we're getting closer to the first or last occurrence we want.

At the end, we either did not find the element, so return our default -1 from the temporary result, or we have the exact first or last location of the element there.

This logic is easily implemented iteratively, otherwise in the recursive case we would need to pass an additional variable as input to track the last found occurrence. Up to you whatever road you prefer.

You can check my implementations of binarySearchFirstOccurrence and binarySearchLastOccurrence on my Gist alongside tests in BinarySearchFirstOccurrenceJTests and BinarySearchLastOccurrenceJTests

For the recursive version check out instead binarySearchFirstOccurrenceRecursive and binarySearchLastOccurrenceRecursive on my Gist alongside tests in BinarySearchFirstOccurrenceRecursiveJTests and BinarySearchLastOccurrenceRecursiveJTests

 

Note that the code has been tweaked to make it generic, and can be further improved by accepting a Comparator in input, which would allow the search to work correctly also for elements that are not following natural ordering.

[Java] Binary search on array

While doing another exercise, I needed to use binary search on an array and I realised I never published any code for that.

Let's remedy this. Important things to remember: array MUST be sorted, if not the logic makes no sense, finally the magic formula:

int mid = floor + ((ceil - floor) / 2);

Burn it in your mind and you'll forever be good to go. 

That's necessary because we alternate between sections of the array, so we won't always start from floor at position 0 and therefore need to offset our starting position everytime to the new floor.

Also I was checking how to make it generic, the change would simply be to modify the declaration of the method to:

 public static <T> int binarySearch(T[] elements, T element)  

And then invoke as:

 ArrayUtils.<TYPE>binarySearch(collection, element)  

However, since you are comparing elements in the collection, your generic type MUST offer the compareTo method to be used in place of integer comparison.

You can find my implementation of binarySearch for integer arrays on my Gist along with some tests in BinarySearchJTests.
An iterative version is proposed in binarySearchIterative along with some tests in BinarySearchIterativeJTests.

[Java] Find minimum highest calculated value in ordered collection

I was searching from some problems online and found a video that poses an interesting one.

We handle Apartment objects that look like this:

Apartment:{

  "gym": false,

  "school": true,

  "store": false

} 

The values true/false indicate that the specific facility is present (true) or not (false) at that apartment. If a facility is present at an apartment, the travel distance from the apartment to the facility is 0.

If a facility is not present at an apartment, it might be present at a farther apartment. In that case, the travel distance is equal to the number of apartments you must cross to reach that facility.

An array of Apartments is given in input as well as a collection of facilities that are relevant for us, for example:

["gym","school"]

The goal of the exercise is to find which apartment minimizes the maximum travel distance to any relevant facility (return its index in the input array).

If an apartment has two facilities at distances N and M, the maximum travel distance is the max(N,M), NOT the sum.

If multiple apartments satisfy the requirement, return any of them.

I also added an additional requirement, if NO apartment satisfies the requirements (eg a relevant facility is NOT present at any apartment), return -1.