Binary Search Modifications

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

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;
	}