StudentSquare.in

Binary Search

Detailed Discussion


1)What is Binary Search ?
  A binary search is an advanced type of search algorithm that finds and fetches data from a sorted list of items. Its core working principle involves dividing the data in the list to half until the required value is located and displayed to the user in the search result. Binary search is commonly known as a half-interval search or a logarithmic search.

2)What is the complexity of Binary Search ?
  Binary search is a fast search algorithm with run-time complexity of Ο(log n).   Here, n is the number of elements in the linear array or size of the array.

3)How Binary Search works?
  Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.

This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.

4)When Binary Search Algorithm is applied ?
 

  1. Binary search works efficiently on sorted data no matter the size of the data.

  2. Instead of performing the search by going through the data in a sequence, the binary algorithm randomly accesses the data to find the required element. This makes the search cycles shorter and more accurate.

  3. Binary search performs comparisons of the sorted data based on an ordering principle than using equality comparisons, which are slower and mostly inaccurate.

  4. After every cycle of search, the algorithm divides the size of the array into half hence in the next iteration it will work only in the remaining half of the array.