# HelloKoding

Practical coding guides

# Binary Search Algorithm

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

## What is Binary Search Algorithm

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

BinarySearch.java

``````package com.hellokoding.algorithm;

public class BinarySearch {
public static int binarySearch(int T, int[] A) {
int N = A.length;
int L = 0;
int R = N - 1;

while (L <= R) {
int M = (int)Math.floor((L+R)/2);
if (A[M] < T)
L = M + 1;
else if (A[M] > T)
R = M - 1;
else
return M;
}

return -1;
}
}
``````

## Complexity

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