Binary Search - Revision history

Admin at 01:36, 20 July 2017

2017-07-20T01:36:47Z

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

	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

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

Admin at 01:36, 20 July 2017

2017-07-20T01:36:33Z

← Older revision		Revision as of 01:36, 20 July 2017
Line 8:		Line 8:
	* One-sided binary search can be performed for a given key, looking for a nearby key, by a two-step process: first, the one-sided search window is progressively doubled - we look at the interval data[thisindex + 1], and if it is not greater than the key we are looking for, we look at data[thisindex + 2], then data[thisindex + 4], then data[thisindex + 8], then data[thisindex + 16], stopping when the key we examine is greater than the target key. We then perform a binary search using the lower and upper bounds. This runs with 2 log n operations max.		* One-sided binary search can be performed for a given key, looking for a nearby key, by a two-step process: first, the one-sided search window is progressively doubled - we look at the interval data[thisindex + 1], and if it is not greater than the key we are looking for, we look at data[thisindex + 2], then data[thisindex + 4], then data[thisindex + 8], then data[thisindex + 16], stopping when the key we examine is greater than the target key. We then perform a binary search using the lower and upper bounds. This runs with 2 log n operations max.

			=Modifications to Binary Search=

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

	=Flags=		=Flags=

	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

Admin at 09:47, 16 July 2017

2017-07-16T09:47:01Z

← Older revision		Revision as of 09:47, 16 July 2017
Line 7:		Line 7:
	* Modified binary search (aforementioned, remove equals and tend right or tend left) can work as a "find greatest element less than this key" or "find least element greater than this key"		* Modified binary search (aforementioned, remove equals and tend right or tend left) can work as a "find greatest element less than this key" or "find least element greater than this key"
	* One-sided binary search can be performed for a given key, looking for a nearby key, by a two-step process: first, the one-sided search window is progressively doubled - we look at the interval data[thisindex + 1], and if it is not greater than the key we are looking for, we look at data[thisindex + 2], then data[thisindex + 4], then data[thisindex + 8], then data[thisindex + 16], stopping when the key we examine is greater than the target key. We then perform a binary search using the lower and upper bounds. This runs with 2 log n operations max.		* One-sided binary search can be performed for a given key, looking for a nearby key, by a two-step process: first, the one-sided search window is progressively doubled - we look at the interval data[thisindex + 1], and if it is not greater than the key we are looking for, we look at data[thisindex + 2], then data[thisindex + 4], then data[thisindex + 8], then data[thisindex + 16], stopping when the key we examine is greater than the target key. We then perform a binary search using the lower and upper bounds. This runs with 2 log n operations max.


			=Flags=

			{{AlgorithmsFlag}}

Admin: /* Skiena Chapter 4 */

2017-07-16T09:46:43Z

Skiena Chapter 4

← Older revision		Revision as of 09:46, 16 July 2017
Line 3:		Line 3:
	==Skiena Chapter 4==		==Skiena Chapter 4==

	See [[Search#Skiena Chapter 4]] for some variations on binary search. Important aspects of this are repeated here:		See [[Algorithms/Search#Skiena Chapter 4]] for some variations on binary search. Important aspects of this are repeated here:
	* You can use binary search to find the starting point of a run of repeated keys, but you can also use a modified binary search (tends right, no equals) to return the right boundary of the run.		* You can use binary search to find the starting point of a run of repeated keys, but you can also use a modified binary search (tends right, no equals) to return the right boundary of the run.
	* Modified binary search (aforementioned, remove equals and tend right or tend left) can work as a "find greatest element less than this key" or "find least element greater than this key"		* Modified binary search (aforementioned, remove equals and tend right or tend left) can work as a "find greatest element less than this key" or "find least element greater than this key"
	* One-sided binary search can be performed for a given key, looking for a nearby key, by a two-step process: first, the one-sided search window is progressively doubled - we look at the interval data[thisindex + 1], and if it is not greater than the key we are looking for, we look at data[thisindex + 2], then data[thisindex + 4], then data[thisindex + 8], then data[thisindex + 16], stopping when the key we examine is greater than the target key. We then perform a binary search using the lower and upper bounds. This runs with 2 log n operations max.		* One-sided binary search can be performed for a given key, looking for a nearby key, by a two-step process: first, the one-sided search window is progressively doubled - we look at the interval data[thisindex + 1], and if it is not greater than the key we are looking for, we look at data[thisindex + 2], then data[thisindex + 4], then data[thisindex + 8], then data[thisindex + 16], stopping when the key we examine is greater than the target key. We then perform a binary search using the lower and upper bounds. This runs with 2 log n operations max.

Admin: Created page with "=Notes= ==Skiena Chapter 4== See Search#Skiena Chapter 4 for some variations on binary search. Important aspects of this are repeated here: * You can use binary search t..."

2017-07-16T09:46:30Z

Created page with "=Notes= ==Skiena Chapter 4== See Search#Skiena Chapter 4 for some variations on binary search. Important aspects of this are repeated here: * You can use binary search t..."

New page

=Notes=

==Skiena Chapter 4==

See [[Search#Skiena Chapter 4]] for some variations on binary search. Important aspects of this are repeated here:
* You can use binary search to find the starting point of a run of repeated keys, but you can also use a modified binary search (tends right, no equals) to return the right boundary of the run.
* Modified binary search (aforementioned, remove equals and tend right or tend left) can work as a "find greatest element less than this key" or "find least element greater than this key"
* One-sided binary search can be performed for a given key, looking for a nearby key, by a two-step process: first, the one-sided search window is progressively doubled - we look at the interval data[thisindex + 1], and if it is not greater than the key we are looking for, we look at data[thisindex + 2], then data[thisindex + 4], then data[thisindex + 8], then data[thisindex + 16], stopping when the key we examine is greater than the target key. We then perform a binary search using the lower and upper bounds. This runs with 2 log n operations max.