Binary Search: Difference between revisions
From charlesreid1
(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...") |
|||
| 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. | ||
Revision as of 09:46, 16 July 2017
Notes
Skiena Chapter 4
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.
- 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.