# Insight Through Computing 26. Divide and Conquer Algorithms Binary Search Merge Sort Mesh Generation...

date post

17-Dec-2015Category

## Documents

view

213download

0

Embed Size (px)

### Transcript of Insight Through Computing 26. Divide and Conquer Algorithms Binary Search Merge Sort Mesh Generation...

- Slide 1
- Insight Through Computing 26. Divide and Conquer Algorithms Binary Search Merge Sort Mesh Generation Recursion
- Slide 2
- Insight Through Computing An ordered (sorted) list The Manhattan phone book has 1,000,000+ entries. How is it possible to locate a name by examining just a tiny, tiny fraction of those entries?
- Slide 3
- Insight Through Computing Key idea of phone book search: repeated halving To find the page containing Pat Reeds number while (Phone book is longer than 1 page) Open to the middle page. if Reed comes before the first entry, Rip and throw away the 2 nd half. else Rip and throw away the 1 st half. end
- Slide 4
- Insight Through Computing What happens to the phone book length? Original: 3000 pages After 1 rip: 1500 pages After 2 rips: 750 pages After 3 rips: 375 pages After 4 rips: 188 pages After 5 rips: 94 pages : After 12 rips: 1 page
- Slide 5
- Insight Through Computing Binary Search Repeatedly halving the size of the search space is the main idea behind the method of binary search. An item in a sorted array of length n can be located with just log 2 n comparisons.
- Slide 6
- Insight Through Computing Binary Search Repeatedly halving the size of the search space is the main idea behind the method of binary search. An item in a sorted array of length n can be located with just log 2 n comparisons. Savings is significant! n log2(n) 100 7 100010 1000013
- Slide 7
- Insight Through Computing 121535334245517362 758698 Binary search: target x = 70 v L: Mid: R: 1 6 12 1 2 3 4 5 6 7 8 9 10 11 12 v(Mid)

Recommended

*View more*