# Binary Search Modifications

### From charlesreid1

Modifications to binary search include:

- Finding the left-most occurrence of an item
- Finding the right-most occurrence of an item
- One-sided binary search

## Contents

## Finding Left-Most/Right-Most Occurrence

Let's suppose we have an array with multiple occurrences of an item:

[3, 3, 3, 11, 11, 11, 11, 11, 1789, 1791]

Now, if we do a binary search for 11, it will return position 4:

$ java BinarySearch.java Binary search for 11: 4

But this is only one of several occurrences. The first is at index 3. We can modify the binary search algorithm to return the *first* occurrence of 11, by modifying the binary search algorithm so that it does not stop when it finds an item that is equal. This will cause binary search to continue, even when it finds a match.

When we do this, we must decide whether the algorithm will move left or right when it finds an item that is equal. This is determined by the "default" case for the if/else statement. Here are two examples of a left-most occurrence and right-most occurrence method in Java:

### Classic Binary Search

Start with the plain binary search algorithm - our left and right side algorithm will be based on this.

(Note: this is implemented in a generic class that takes a type `<T extends Comparable<T>>`

.

/** Perform a binary search to find target in array of data. * * This returns the (negative) insertion index * if the target is not found. */ public int binarySearch(T target) { // Start by defining your lo/hi index int lo = 0; int hi = data.length-1; // Mid gets defined here because it will become // the insertion index if we don't find target int mid = (data.length)/2; // Can use while loop, or recursive structure while(lo<hi) { // Need to re-define mid each time mid = (lo+hi)/2; // Classic, man. if(target.compareTo(data[mid]) < 0) { // Move left hi = mid-1; } else if(target.compareTo(data[mid]) > 0) { // Move right lo = mid+1; } else { // This equals case is treated separately here. // Depending on whether we move it into the // first or second if clauses above, we get // our left/right boundary search methods instead. return mid; } } // Insertion index return -(mid+1); }

### Right Boundary Search

/** Search for the right boundary of a run of objects. * * This works basically the same as binary search, * except we don't have an equals to stop us, and we * default to moving right. * * To return the right boundary, return hi instead of mid. */ public int binaryRightBoundarySearch(T target) { // Start by defining your lo/hi index int lo = 0; int hi = data.length-1; int mid = (data.length)/2; // Can use while loop, or recursive structure while(lo<=hi) { // Need to re-define mid each time mid = (lo+hi)/2; // Classic, man. if(target.compareTo(data[mid]) < 0) { // Move left hi = mid-1; } else { // Move right by default. // This includes the equals case! lo = mid+1; } } // Above loop won't stop, // we always get here. return hi; }

### Left Boundary Search

/** Search for the left boundary of a run of objects. * * To return the left boundary, return lo+1 instead of mid. */ public int binaryLeftBoundarySearch(T target) { // Start by defining your lo/hi index int lo = 0; int hi = data.length-1; int mid = (data.length)/2; // Can use while loop, or recursive structure while(lo<hi) { // Need to re-define mid each time mid = (lo+hi)/2; // Classic, man. if(target.compareTo(data[mid]) > 0) { // Move right lo = mid + 1; } else { // Move left by default. // This includes the equals case! hi = mid-1; } } return lo; }

## Flags

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity Amortization Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |