# Binary Search

Tue Feb 08 2022 13:03:48 GMT+0000 (Coordinated Universal Time)

```// Iterative Solution : Time Complexity : O(LogN),  Aux. Space : O(1)

import java.util.*;
import java.io.*;

class GFG
{
static int bSearch(int arr[], int n, int x)
{
int low = 0, high = n - 1;

while(low <= high)
{
int mid = (low + high) / 2;

if(arr[mid] == x)
return mid;

else if(arr[mid] > x)
high = mid - 1;

else
low = mid + 1;
}

return -1;
}

public static void main(String args[])
{
int arr[] = {10, 20, 30, 40, 50, 60}, n = 6;

int x = 25;

System.out.println(bSearch(arr, n, x));  // Output : -1

}

}

// Recursive Solution : Time Complexity : O(LogN),  Aux. Space : O(logN)

import java.util.*;
import java.io.*;

class GFG
{
static int bSearch(int arr[], int low, int high, int x)
{
if(low > high)
return -1;

int mid = (low + high) / 2;

if(arr[mid] == x)
return mid;

else if(arr[mid] > x)
return bSearch(arr, low, mid - 1, x);

else
return bSearch(arr, mid + 1, high, x);
}

public static void main(String args[])
{
int arr[] = {10, 20, 30, 40, 50, 60, 70}, n = 7;

int x = 20;

System.out.println(bSearch(arr, 0, n - 1, x));  // Output : 1
}
}```
content_copyCOPY