Standard Searching Algorithms Flashcards
1
Q
What happens in a binary search?
A
- In a binary search, we locate the midpoint of the data set, removing irrelevant halves of our data until we find our piece of data.
2
Q
Example of a binary search - Find the number 26 in the data set (5, 10, 26, 56, 68, 75, 96)
A
- write under each number its index (first one is 0)
- work out the midpoint by adding together the first index in the list and the last index in the list. We then divide that answer by 2
- remove the side that the value isn’t on (all the values to the right of 56 (the midpoint) as we know 56 is bigger than 26)
- find the midpoint of the new list and round down if it’s a decimal.
-index 1 = 10 so get rid of values left of 10 and find the new midpoint
- = 2. Index 2 = 26. 3 searches
3
Q
What happens in a linear search?
A
- We go down the list checking each piece of data in turn until we find the data we’re looking for.
- If we check a piece of data and it is not the one we’re looking for, we move onto the next one.
- The data doesn’t need to be in order.
4
Q
Example of a linear search - find 26 in: 75, 10, 26, 97, 68, 5, 56
A
- First piece = 75
- Second piece = 10
- Third piece = 26
- 26 is what we’re looking for. Three searches.
5
Q
Advantages of a binary search -
A
- Better for searching through large data sets as it is quicker in locating data (reduces size of list)
- It’s a fairly simple and straightforward searching algorithm to use
6
Q
Disadvantages of a binary search -
A
- Not effective for searching through smaller data sets as it overcomplicates the problem and therefore would take longer.
- Only works on sorted lists.
7
Q
Advantages of a linear search -
A
- Can be used on any list, whether it’s sorted or unsorted
- Better for searching through small data sets
8
Q
Disadvantages of a linear search -
A
- Ineffective when used on a large data set, as checking each piece of data on large data sets can be time consuming.
