diff options
| -rw-r--r-- | 04-10.md | 4 | ||||
| -rw-r--r-- | 04-13.md | 295 |
2 files changed, 299 insertions, 0 deletions
@@ -174,3 +174,7 @@ The following is listed from most to least efficient - Exponential O(2^n) or O(k^n) - Factorial O(n!) - Anything worse than Exponential (actually, even quadratic) are considered pretty bad + +--- + +[-> 04/13](04-13.md) diff --git a/04-13.md b/04-13.md new file mode 100644 index 0000000..937fe4a --- /dev/null +++ b/04-13.md @@ -0,0 +1,295 @@ +[\<- 04/10](04-10.md) + +--- + +## So far ... + +We have discussed contents in Chapter 1 +1. Concept of data Structure +2. Algorithm Efficiency - big O notation + +# Search + +## First Data Structure + +- You've seen it before: an array! +- How is an array laid out? + +|[] |[] |[] |[] |[] | +|-|-|-|-|-| +|0|1|...|...|m-1| + +- a series of data laid in **consecutive** memory locations +- picture of slots... starting at "zero" +- m slots, so the end is at "m-1" + +## Arrays - Precondition + +- Pre-condition - n existing elements + - If we want to store n (0 <= n <= m) elements in the array, we place them in slots "0" through "n-1" + +|x|x|x|x|x|[]|[]|[]| +|-|-|-|-|-|--|--|--| +|0|1|...|...|n-1|...|...|m-1| + +## Arrays - Insert + +- Your first operation: insert + - It's easiest to add a new element at the end of the array + +|x|x|x|x|x|[]|[]|[]|[]| +|-|-|-|-|-|--|--|--|--| +|0|1|...|...|n-1|n|...|...|m-1| + +- To add the element x, we could do + +``` +a[n] = x; +n++; +``` + +Or, alternatively +``` +a[n++] = x; +``` + +- What is the big-O runtime of this operation? + - O(1) (no repeating operations) + +## Arrays - Access/Retrieve + +- Second operation: Access/Retrieve + - **Indexing** - Retrieve an element through indexing: O(1) + - What about **searching a given value**? + +|x|x|x|x|x|[]|[]|[]| +|-|-|-|-|-|--|--|--| +|0|1|...|...|n-1|...|...|m-1| + +- How to retrieve an element through an index +``` +x = a[i]; +``` + +- How to search for a given value? + - We'll cover this soon + +## Let's Play a Game + +Let's look for Matt in this array + +|?|?|?|?|?| +|-|-|-|-|-| +|0|1|2|3|4| + +Logically, we would check each index for Matt + +- Check the first index (i=0) + +|Chris|?|?|?|?| +|-|-|-|-|-| +|0|1|2|3|4| + +- Comapare "Chris" to "Matt" + - They do not match, so now we move on to the next value + +|Chris|Rachael|?|?|?| +|-|-|-|-|-| +|0|1|2|3|4| + +- Keep Checking + +|Chris|Rachael|Ryan|?|?| +|-|-|-|-|-| +|0|1|2|3|4| + +- Keep Checking + +|Chris|Rachael|Ryan|Mike|?| +|-|-|-|-|-| +|0|1|2|3|4| + +- Keep Checking + +|Chris|Rachael|Ryan|Mike|Brian| +|-|-|-|-|-| +|0|1|2|3|4| + +- Unsuccessful search - but What's the runtime? + - it takes n comparisons -> O(n) + - if we were looking for Chris, it would only take one comparison + - this is called the best case O(1) + - If we were looking for Brian, it would take five comparisons (or n comparisons) + - this is called the worst case O(n) + - How many comparisons will a successful search require on average? (Keep this question in mind) + +## Sequential Search + +- Searching an array: start with the first element and proceed to the last element +- Code: + +``` +int found = 0; +//assume the array 'a' is 'n' elements long +//assume 'x' is the search term + +for(i = 0; i < n; i++){ + if(a[i] == x){ + found = 1; + break; + } +} +``` + +- The break statement is important so that the big-O is O(1) instead of O(n) for best case + - More efficient +- Reminder: to use booleans (found = false) include stdbool.h + +## Sequential Search: how to stop + +- We can stop after finding first match +- Two ways to do that + - Add a "break" inside the loop when found (see the previous example) + - break means exit the innermost loop + - make the for loop look like this: `for(i=0; i<n && !found; i++)` +- You **should NOT** combine them. You **lose points** in clarity if you do that in the assignment. Pick which approach you like, or use a while, but do not use both techniques + +--- + +The Big O notation? +- It depends on the sequence to search (i.e. input) +- The best case? O(1) + - search is located at the beginning of the array +- The worst case? O(n) + - search is at the end or not in the array + +On average, how many tries to find a given item? +- On average it takes you n/2 tries + +Why? +- In general, if you want an average, you add up everything and divide by the number of something... so search in 1 step, 2 steps,... n steps gives us (1+2+3...+n)/n -> n/2 is a nice shortcut + +- So what's the Big-O notation + - O(n/2) -> O(n) + +## Arrays - Sequential Search - Summary + +- This searching algorithm is called "linear search" or "sequential search" +- It's big-O runtime is O(n) + - best case O(1) + - average case O(n) + - worst case O(n) +- The military wouldn't be happy if you told them that *on average* the missile defense system stops the missiles + - The worst case big-O is the one we care most! +- Can we improve this? + +## Arrays Probability Search + +- A game again!! + +|Chris|Rachael|Ryan|Mike|Brian| +|-|-|-|-|-| +|0|1|2|3|4| + +- How to improve the search algorithm? + - Let's say we want to find Mike + - We can add a swap to move Mike closer to the beginning in case he is searched for again + +|Chris|Rachael|Mike|Ryan|Brian| +|-|-|-|-|-| +|0|1|2|3|4| + +- If we look for Mike again, it will take one less comparison to find him + +|Chris|Mike|Rachael|Ryan|Brian| +|-|-|-|-|-| +|0|1|2|3|4| + +- If we look for Mike a third time, it will take one more less comparison to find him + +|Mike|Chris|Rachael|Ryan|Brian| +|-|-|-|-|-| +|0|1|2|3|4| + +- Now that Mike is at the front, he is the best case + +--- + +- Note + - Be careful not to swap the first person with the non-existent preceding person +- This is called a "move to front heuristic" + - Heuristics are things that probably help, but not certain they would + - This is in the book called "probability search" +- Example: having an application in your cache and therefore it runs faster +- Will this improve unsuccessful searches? + - Worst case is still n. The average time probably improves, but is still O(n) + +- You will do sequential search in Project 3 + +## Arrays - Another Search Type + +Let's play a game: +- Pick a number from 1-100 +- Tell a guesser whether he us too high or too low +- I claim I can guess in 7 or less + +1. Guess 50 + - "50 is too high" -> now we know the number is 1-49 + - In one guess, the range is cut in half + +2. Guess 25 + - "25 is too low" -> now we know the number is 26-49 + - In two guesses, the range is cut down to 1/4 of the original range + +## Binary Search + +- Idea: we halve the space over which we search +- At each step, we eliminate 1/2 of the remaining possibilities +- Maximum number of steps required is O(log(n)) if the original size of the space was n + - Theoretically faster than sequential search +- This algorithm is called **binary search** +- Pre-condition: + - It has to be **sorted**, otherwise we couldn't get rid of an entire sub-range + +## Binary Search - Code + +- side note: be clear on counter/variable names + +``` +//return true if 'x' is in 'a[]', false if not; 'n' is the length of 'a[]' +bool bsearch(int a[], int n, int x){ + + int lo, hi, mid; + lo = 0; + hi = n-1; + + while(lo <= hi){ + mid = (lo + hi)/2; //updates every iteration + if(a[mid] == x) return true; + if(a[mid] > x) hi = mid-1; + else lo = mid+1; + } + + return false; + +} +``` + +## Binary Search - Big-O + +- If you are halving each time, how long does the loop run? + - O(log(n)) + - O(log(n)) beats the pants off linear O(n) + - log2(1000000) = 20 + +- What is the big-O runtime for binary search? + - Best case? O(1) + - Worst case? O(log(n)) + - Of course, we care the most about the worst case +- If you were working with strings... you'd just use strcmp() instead of comparisons + +## Binary Search? Sequential Search? + +Is binary search always better than sequential search? +Answer: It depends +- How about if the sequence is not sorted? |