Binary Search
Which type of lists or data sets are linear searching algorithms used for?
Unsorted lists or data sets
A binary search is to be performed on the list:
1 5 10 13 48 68 100 101
How many comparisons would it take to find number 101?
4
How many linear searches will it take to find the value 7 in the list [1,4,8,7,10,28]?
4
Describe a disadvantage of a binary search algorithm ?
More complicated to code than a linear search.
Which type of lists or data sets are binary searching algorithms used for?
Sorted lists or data sets
How many binary searches will it take to find the value 7 in the list [1,4,7,8,10,28]?
1
How many linear searches will it take to find the value "Fred" in the list [Mary, George, Alison, Mabel, Sarah, Steve, Fred]?
7
Describe an advantage of a binary search algorithm ?
Quicker than a linear search.
What is time Complexity of Binary Search?
O(log n)
How many binary searches will it take to find the value 10 in the list [1,4,9,10,11]?
2
What is Linear Algorithm?
Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.
Describe an advantage of a binary search algorithm ?
Performs well over large ordered lists.
What is Decomposition?
breaking down a large problem into smaller sub-problems.
What is the maximum number of comparisons required to find a value in a list of 20 items using a binary search?
5
What is an advantage of the Linear search algorithm?
Performs well with small sized data sets
What is Binary Search?
Put the elements in order, compare with the middle value, split the list in order and repeat.
A binary search is to be performed on the list:
3 5 9 10 23
How many comparisons would it take to find number 9?
1
What is Time Complexity of Linear Search Algorithm ?
O(n)