What is a binary search? Write its properties.

Q.) What is a binary search? Write its properties.

 Subject: Data Structures

Answer:

A binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

Here's a step-by-step approach to how a binary search works:

  1. Find the middle element of the array. If the array has an odd number of items, the middle item is the (length of array / 2) + 1th item. If the array has an even number of items, there are two middle items, and you can pick either.

  2. If the middle element is the target, the search is done.

  3. If the target is less than the middle element, continue the search in the lower half of the array.

  4. If the target is greater than the middle element, continue the search in the upper half of the array.

  5. Repeat steps 1-4 on the new range.

Properties of Binary Search:

  1. Time Complexity: The time complexity of Binary Search can be written as T(n) = T(n/2) + c. The time complexity of Binary Search is O(log n).

  2. Space Complexity: The space complexity of Binary Search for iterative implementation is O(1) in the worst case. For recursive implementation, space complexity is O(log n).

  3. Search Speed: Binary search is much faster than linear search. In binary search, the number of elements to be searched gets halved each time.

  4. Sorted Array: Binary search requires the input data to be sorted; if data is not sorted, we need to sort it first.

  5. Diverse Usage: Binary search is used in a lot of programming languages to search data.

  6. Divide and Conquer Strategy: Binary search is an example of a divide and conquer strategy, similar to quick sort and merge sort.

Here's an example of a binary search:

Let's say we have a sorted array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], and we want to find the number 11.

  1. The middle element is 9. 11 is greater than 9, so we only need to search in the upper half of the array.

  2. Now we only consider the array [11, 13, 15, 17, 19]. The middle element is 15. 11 is less than 15, so we only need to search in the lower half of the array.

  3. Now we only consider the array [11, 13]. The middle element is 13. 11 is less than 13, so we only need to search in the lower half of the array.

  4. Now we only consider the array [11]. The middle (and only) element is 11, which is the number we're searching for. So the search is done.