# Binary Search in JAVA

Binary search is a searching technique that is based upon the Divide-and-Conquer Rule.

In this searching technique, a sorted array is divided into two equal halves and then the same technique is applied onto the two halves searching for the element by comparing the high and the low.

 Time Complexity (Best) Ω(1) Time Complexity (Avg) Θ(log n) Time Complexity (Worst) O(log n) Space Complexity O(1)

## Working of binary search in JAVA

1. For Binary Search to be performed on any array, the array must be already sorted in any format, that is, either ascending or descending.
2. Find the middle index of the array/list.
3. If the middle element is equal to the search element, Stop Searching.
4. If the element that is to be searched is less then the middle element then consider the first half as a separate list.
5. Else-If the element that is to be searched is larger then the middle element then consider the second half as a separate list.
6. Repeat Step 2-3-4-5 Until desired result is found.

## Algorithm of Binary Search in Java

• while(left<=right)
mid=left + (right – left)/2;
• if(a[mid]<search_element)
left=mid+1;
• else if(a[mid]>search_element)
right=mid-1;
• If found return index+1
• Else return -1

## Methods Discussed

We will be discussing two methods for the same

• Recursive Approach
• Iterative Approach

## Binary Search in Java (Recursive Approach)

Run
```// Binary Search implimentation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{

public static int binarySearch(int array[], int left, int right, int item){

if (right >= left){

// calculation of new mid
int mid = left + (right - left)/2;

// returns position where found
if (array[mid] == item)
return mid+1;

// goes to recursive calls in left half
if (array[mid] > item)
return binarySearch(array, left, mid-1, item);

// goes to recursive calls in right half
else
return binarySearch(array, mid+1, right, item);
}
else
return -1;
}
public static void main(String args[]){

int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
int item = 70;
int size = array.length;

int position = binarySearch(array, 0, size-1, item);

if(position == -1)
else
System.out.println("The value " + item + " found at position: " + position);

}
}
// Time complexity O(Log N)
```

### Output

`The value 70 found at position: 7`

## Binary Search in Java (Iterative Approach)

Let us look at the iterative approach below –

Run
```// Binary Search implementation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{

public static int binarySearch(int arr[], int left, int right, int item){

while (left <= right) {
int mid = left + (right - left) / 2;

// if item is at mid
if (arr[mid] == item)
return mid;

// If item greater, ignore left half, consider only right half
if (arr[mid] < item)
left = mid + 1;

// If item is smaller, ignore right half, consider only left half
else
right = mid - 1;
}

// if we are able to reach here
// means item wasn't present
return -1;
}
public static void main(String args[]){

int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
int item = 70;
int size = array.length;

int position = binarySearch(array, 0, size-1, item);

if(position == -1)
else
System.out.println("The value " + item + " found at position: " + position);

}
}```

### Output

`The value 70 found at position: 6`

O(1)

O(log n)

O(log n)

O(1)

## Searching

Searching algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.