Algorithms/Search - Revision history

Admin: Fix math syntax: replace floor() with proper \lfloor/\rfloor LaTeX notation; remove unnecessary braces from \log{(n)} (via update-page on MediaWiki MCP Server)

2026-06-06T00:17:40Z

Fix math syntax: replace floor() with proper \lfloor/\rfloor LaTeX notation; remove unnecessary braces from \log{(n)} (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 00:17, 6 June 2026
Line 16:		Line 16:

	<math>		<math>
	(mid - 1) - low + 1 = ~~floor(~~ \dfrac{low+high}{2} ) - low \leq \dfrac{high - low + 1}{2}		(mid - 1) - low + 1 = \left\lfloor \dfrac{low+high}{2} \right\rfloor - low \leq \dfrac{high - low + 1}{2}
	</math>		</math>

Line 22:		Line 22:

	<math>		<math>
	high - (mid+1) + 1 = high - ~~floor(~~ \dfrac{low + high}{2} ) \leq \dfrac{high - low + 1}{2}		high - (mid+1) + 1 = high - \left\lfloor \dfrac{low + high}{2} \right\rfloor \leq \dfrac{high - low + 1}{2}
	</math>		</math>

Line 31:		Line 31:
	</math>		</math>

	In other words, <math>r > \log{(n)}</math>		In other words, <math>r > \log(n)</math>

	Thus, we have		Thus, we have

	<math>		<math>
	r = ~~floor(~~ \log{(n)~~} )~~ + 1		r = \lfloor \log(n) \rfloor + 1
	</math>		</math>

Admin: /* Flags */

2017-07-20T01:36:31Z

Flags

← Older revision		Revision as of 01:36, 20 July 2017
Line 92:		Line 92:

	The cost of this one-sided search is maximum 2 log p comparisons, where p is the width of the interval.		The cost of this one-sided search is maximum 2 log p comparisons, where p is the width of the interval.

			=Modifications to Binary Search Algorithm=

			We can make modifications to the binary search algorithm to perform other useful tasks like counting duplicates. See [[Binary Search Modifications]] page.

	=Flags=		=Flags=

Admin: /* One-Sided Binary Search */

2017-07-16T06:22:46Z

One-Sided Binary Search

← Older revision		Revision as of 06:22, 16 July 2017
Line 90:		Line 90:

	Once a key greater than the search key is found, you have your search range, i to i+X, where X is a power of 2. You can now call binary search using those as your low and high indices, and find your key.		Once a key greater than the search key is found, you have your search range, i to i+X, where X is a power of 2. You can now call binary search using those as your low and high indices, and find your key.

			The cost of this one-sided search is maximum 2 log p comparisons, where p is the width of the interval.

	=Flags=		=Flags=

Admin: /* One-Sided Binary Search */

2017-07-16T04:31:32Z

One-Sided Binary Search

← Older revision		Revision as of 04:31, 16 July 2017
Line 85:		Line 85:
	===One-Sided Binary Search===		===One-Sided Binary Search===

			Another modification that can be made to the binary search procedure is an '''expanding''' search window that doubles with each step. This is a useful procedure if you are at a particular point and you are searching for a neighboring key.

			Start by looking at the next item over, data[i+1], and performing a check if it is greater than the search key. If not, look two items over, data[i+2], and see if that key is greater than the search key. If not, look at data[i+4], then data[i+8], then data[i+16], and so on.

	a ~~modified~~ binary search.		Once a key greater than the search key is found, you have your search range, i to i+X, where X is a power of 2. You can now call binary search using those as your low and high indices, and find your key.


	=Flags=		=Flags=

Admin: /* Finding Greatest Element Less Than/Least Element Greater Than Key */

2017-07-16T04:00:47Z

Finding Greatest Element Less Than/Least Element Greater Than Key

← Older revision		Revision as of 04:00, 16 July 2017
Line 60:		Line 60:

	<pre>		<pre>
	~~binary search~~(data, key, lo, hi):		def binary_search(data, key, lo, hi):

	~~int middle~~
	if( low > high):		if( low > high):
	return -1 // key not found		return -1 // key not found
Line 68:		Line 67:
	mid = (lo + hi)/2		mid = (lo + hi)/2

	// if( data[mid] ~~equals~~ key)		// if( data[mid] == key):
	// return mid // we remove this for our purposes		// return mid // we remove this for our purposes

	// if we want to move right by default:		// if we want to move right by default:
	if( data[mid] > key ):		if( data[mid] > key ):
	return ~~binary search~~(data, key, lo, mid-1)		return binary_search(data, key, lo, mid-1)
	else		else
	return ~~binary search~~(data, key, mid+1, hi)		return binary_search(data, key, mid+1, hi)

	// if we want to move left by default:		// if we want to move left by default:
	if( data[mid] < key ):		if( data[mid] < key ):
	return ~~binary search~~(data, key, mid+1, hi)		return binary_search(data, key, mid+1, hi)
	else		else
	return ~~binary search~~(data, key, lo, mid-1)		return binary_search(data, key, lo, mid-1)
	</pre>		</pre>

Admin: /* Finding Greatest Element Less Than/Least Element Greater Than Key */

2017-07-16T03:59:43Z

Finding Greatest Element Less Than/Least Element Greater Than Key

← Older revision		Revision as of 03:59, 16 July 2017
Line 61:		Line 61:
	<pre>		<pre>
	binary search(data, key, lo, hi):		binary search(data, key, lo, hi):

	int middle		int middle
	if( low > high):		if( low > high):
	return -1 // key not found		return -1 // key not found

	mid = (lo + hi)/2		mid = (lo + hi)/2

	// if( data[mid] equals key)		// if( data[mid] equals key)
	// return mid // we remove this for our purposes		// return mid // we remove this for our purposes

Admin: /* Binary Search and Related Algorithms */

2017-07-16T03:59:24Z

Binary Search and Related Algorithms

@@ Line 45: / Line 45: @@
 ==Skiena Chapter 4==
-===Binary Search and Related Algorithms===
+===Binary Search ===
 Binary search is a fast algorithm for finding a key k in a sorted array S of keys. Binary search begins by looking at the middle key. If it is less than the target, it repeats the process on the second half of the array instead of the entire array; if it is larger than the target, it repeats the process on the first half of the array. It proceeds until it is examining a single element, in which case it either finds the key or not.
@@ Line 54: / Line 54: @@
 Overall, counting occurrences takes log time, regardless of size of run of identical keys (so, e.g., worst case 90% of your keys are the same, this algorithm won't break a sweat).
 ===One-Sided Binary Search===

Admin at 03:53, 16 July 2017

2017-07-16T03:53:07Z

@@ Line 41: / Line 41: @@
 which implies that binary search runs in O(log N) time.
@@ Line 47: / Line 66: @@
 {{AlgorithmsFlag}}
-[[Cateory:Recursion]]
+[[Category:Recursion]]
 [[Category:Search]]

Admin at 00:41, 12 July 2017

2017-07-12T00:41:47Z

← Older revision		Revision as of 00:41, 12 July 2017
Line 43:		Line 43:


			=Flags=


	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

Admin at 00:41, 12 July 2017

2017-07-12T00:41:11Z

@@ Line 2: / Line 2: @@
 ==Goodrich chapter 4==
 Recursion: binary search analysis.
@@ Line 38: / Line 40: @@
 which implies that binary search runs in O(log N) time.