In this tutorial, you will learn about Binary Search Algorithm, how it works and how to implement it with Java

What is Binary Search?

Binary Search is an algorithm for finding the position of a target value within a sorted array

How Binary Search works

Binary Search works on sorted array. Let's say you have a sorted array A, middle element is AM, target value is T. The algorithm will compare AM with T

  • If AM = T, return position of AM

  • If AM < T, the search continues with the lower half of the array A

  • If AM > T, the search continues with the upper half of A

Implementation example with Java

Time complexity O(logN)
Space complexity O(N)