Complexity of Binary Search Algorithm - O(log n) - Data Structure

Discussion

• Nihal   -Posted on 01 Apr 16
  Worst case complexity O (log n)
  Best case complexity O( 1 )
  Average case complexity O (log n)
  
  Binary search algorithm:
  
  In binary search, the array should be sorted. First, compare the item to be searched with the middle element of the array. If the item is found, then search end successfully. If not the array is divided into two part. First part contains all elements to the left of middle element and the other second part contains all the elements to the right side of the middle element.
  
  Due to sorted array, all the element in the first part will be smaller than the middle element and all the element in the second part will be greater than the middle element. If the item to be searched is less than the middle element, then this item will be in first half otherwise it will be in the second half. This process will be continue till we find the required item or get a subarray which does not have any element.

➨ Post your comment / Share knowledge