Binary Search
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:
1 5 10 13 48 68 100 101
How many comparisons would it take to find number 101?
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
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
Describe an advantage of a binary search algorithm ?
Performs well over large ordered lists.
A sorting algorithm is used to locate a specific item in a larger collection of data.
True
OR
False
False
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 the difference between inorder traversal of a binary search tree and a preorder traversal?
In order traversal processes the left subtree, then the root node, then the right subtree, whereas preorder processes the root node, left subtree, then right subtree.
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
Justify why the following modified version of binarySearch() works. Prove that if the key is in the array, it correctly returns the smallest index i such that a[i] = key; if the key is not in the array, it returns -i where i is the smallest index such that a[i] > key.
// precondition array a in ascending order
public static int binarySearch(long[] a, long key) {
int bot = -1;
int top = a.length;
while (top - bot > 1) {
int mid = bot + (top - bot) / 2;
if (key > a[mid]) bot = mid;
else top = mid;
}
if (a[top] == key) return top;
else return -top - 1;
} The while loop invariant says top >= bot + 2. This implies bot < mid < top. Hence length of interval strictly decreases in each iteration. While loop also maintains the invariant: a[bot] < key <= a[top], with the contention that a[-1] is -infinity and a[N] is +infinity.