# 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.

## 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(low<=high)
mid=(low+high)/2;
• if(a[mid]<search_element)
low=mid+1;
• else if(a[mid]>search_element)
high=mid-1;
• If found return index
• Else return -1

## Program of Binary Search in JAVA

```import java.util.*;
class Main {
int search(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;

if (arr[m] == x)    //if x is in the middle
return m;
if (arr[m] < x) //if x is greater, search the right half
l = m + 1;
else         //if x is smaller, search the left half
r = m - 1;
}
}
public static void main(String args[])
{
Main s=new Main();
Scanner sc= new Scanner(System.in);
System.out.println("Enter the element to be searched ");
int num=sc.nextInt();
int arr[]={3,5,6,7,10,14,15,75,88,96,99};
int result = s.search(arr, num);
if (result == -1)
System.out.println("No match found in the Array");
else
System.out.println("Match found at index " + result);
}
}
```
```Enter the element to be searched
96
Match found at index 9```

O(1)

O(log n)

O(log n)

O(1)