Binary Search Modifications - Revision history

Admin: /* Classic Binary Search */

2019-02-01T08:04:47Z

Classic Binary Search

← Older revision		Revision as of 08:04, 1 February 2019
Line 59:		Line 59:
	lo = mid+1;		lo = mid+1;
	} else {		} 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;		return mid;
	}		}

Admin: /* Left Boundary Search */

2019-02-01T08:03:56Z

Left Boundary Search

← Older revision		Revision as of 08:03, 1 February 2019
Line 135:		Line 135:
	} else {		} else {
	// Move left by default.		// Move left by default.
			// This includes the equals case!
	hi = mid-1;		hi = mid-1;
	}		}

Admin: /* Right Boundary Search */

2019-02-01T08:03:46Z

Right Boundary Search

← Older revision		Revision as of 08:03, 1 February 2019
Line 98:		Line 98:
	} else {		} else {
	// Move right by default.		// Move right by default.
			// This includes the equals case!
	lo = mid+1;		lo = mid+1;
	}		}

Admin: /* Left Boundary Search */

2019-02-01T08:03:16Z

Left Boundary Search

← Older revision		Revision as of 08:03, 1 February 2019
Line 111:		Line 111:

	<pre>		<pre>
	/** Search for the ~~letft~~ boundary of a run of objects.		/** Search for the left boundary of a run of objects.
	*		*
	* To return the left boundary, return lo+1 instead of mid.		* To return the left boundary, return lo+1 instead of mid.

Admin: /* Classic Binary Search */

2017-07-20T01:42:47Z

Classic Binary Search

← Older revision		Revision as of 01:42, 20 July 2017
Line 26:		Line 26:

	Start with the plain binary search algorithm - our left and right side algorithm will be based on this.		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 <code><T extends Comparable<T>></code>.

	<pre>		<pre>

Admin: Created page with "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-..."

2017-07-20T01:42:00Z

Created page with "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-..."

New page

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:

<pre>
[3, 3, 3, 11, 11, 11, 11, 11, 1789, 1791]
</pre>

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

<pre>
$ java BinarySearch.java
Binary search for 11: 4
</pre>

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.

<pre>
/** 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 {
return mid;
}
}

// Insertion index
return -(mid+1);
}
</pre>

===Right Boundary Search===

<pre>
/** 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.
lo = mid+1;
}
}

// Above loop won't stop,
// we always get here.
return hi;
}
</pre>

===Left Boundary Search===

<pre>
/** Search for the letft 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.
hi = mid-1;
}
}

return lo;
}
</pre>

==Flags==

{{AlgorithmsFlag}}

[[Category:Search]]
[[Category:Binary Search]]