Define binary search? How can be it stored in computer’s memory as an array? Give suitable example.

Answer: – C program for binary search: This code implements binary search in c language. It can only be used for sorted arrays, but it’s fast as compared to linear search. If you wish to use binary search on an array which is not sorted then you must sort it using some sorting technique say merge sort and then use binary search algorithm to find the desired element in the list. If the element to be searched is found then its position is printed.

Search as the name suggests, is an operation of finding an item from the given collection of items. Binary Search algorithm is used to find the position of a specified value (an ‘Input Key’) given by the user in a sorted list.

Algorithm: –

It starts with the middle element of the list.

  1. If the middle element of the list is equal to the ‘input key’ then we have found the position the specified value.
  2. Else if the ‘input key’ is greater than the middle element then the ‘input key’ has to be present in the last half of the list.
  3. Or if the ‘input key’ is lesser than the middle element then the ‘input key’ has to be present in the first half of the list.

Hence, the search list gets reduced by half after each iteration.

First, the list has to be sorted in non-decreasing order.

[low, high] denotes the range in which element has to be present and [mid] denotes the middle element. Initially low = 0, high = number_of_elements and mid = floor((low+high)/2). In every iteration we reduce the range by doing the following until low is less than or equal to high(meaning elements are left in the array) or the position of the ‘input key’ has been found.

  1. If the middle element (mid) is less than key then key has to present in range [mid+1 , high], so low=mid+1, high remains unchanged and mid is adjusted accordingly
  2. If middle element is the key, then we are done.
  3. If the middle element is greater than key then key has to be present in the range [low,mid-1], so high=mid-1, low remains unchanged and mid is adjusted accordingly.

Properties: –

  1. Best Case performance – The middle element is equal to the ‘input key’ O(1).
  2. Worst Case performance – The ‘input key’ is not present in the list O(logn).
  3. Average Case performance – The ‘input key’ is present, but it’s not the middle element O(logn).
  4. The List should be sorted for using Binary Search Algorithm.
  5. It is faster than Linear Search algorithm, and its performance increases in comparison to linear search as N grows.
Advertisements