Binary Search algorithm

binary-search
search
algorithm

(Team) #1

binary search, also known as half-interval search, logarithmic search or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

Implementation in over 20+ languages: here

Ask our coding community anything.

How this works?

This algorithm takes advantage of the fact that the elements are sorted.

Steps:

  • Compare x with the middle element.
  • If x matches with the middle element, return the mid index.
  • If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
  • (x is smaller) recur in the left half.

Complexity Notation
Worst-case performance O(log n)
Best-case performance O(1)
Average performance O(log n)
Worst-case space complexity O(1)


(Jessica P) #2

Binary search is very important. In fact, this is used for IP address lookup in internet routers.

This is a research paper on this approach.


(Team) #3

Yes, binary search looks to be simple but has huge and varied applications. This is interesting. :grinning:


#4

Actually in some cases it is tricky to determine the final index upon the loop termination. Need much practice to get it super clear.