Binary Search

Question 1

What is a binary search?

Answer 1

It is an efficient algorithm for searching an element in a sorted list or array

It works by repeatedly dividing the search space in half until…
= the target element is found or determined to be absent

It is ideal for large sorted datasets as it has a time
complexity of O(log n).

Note: A time complexity of O(log n) means that the algorithm’s execution time grows logarithmically with the input size, indicating that it is highly efficient for large datasets

Question 2

What are the 5 steps in the binary search process?

Answer 2

1. Start with the middle element of the sorted list
2. If the middle element matches the target:
   = the search is successful
3. If the middle element is greater than the target:
   = repeat the process on the left half of the list
4. If the middle element is smaller than the target:
   = repeat the process on the right half of the list
5. Continue dividing the search space in half:
   = until the target is found, or the search space is empty

Question 3

What is the algorithm in binary search?

Answer 3

1. Start with a list of elements sorted in ascending order (smallest to biggest)
2. Set the left index to the index of the first element (0) and the right index to the index of the last element (n-1)
3. Repeat the following steps while the left index is less than or equal to the right index:
   A) calculate the middle index as the average of the left and right indices.
   B) If the element at the middle index is equal to the target, return the middle index.
   C) If the element at the middle index is less than the target, update the left index to middle index + 1.
   d) If the element at the middle index is greater than the target, update the right index to middle index - 1.
4. If the target is not found:
   = return a special value indicating it was not present in the list

Question 4

What are 4 advantages of binary search?

Answer 4

1. Efficient algorithm with a time complexity of O(log n).
2. Well-suited for large sorted datasets
3. Reduces the search space by half in each iteration
4. If the dataset requires sorting prior to performing multiple searches, the upfront cost of sorting may be outweighed by the overall savings achieved through the efficient binary search algorithm