Breaking
Divide and conquer

# Binary search

Binary search is a method to find the particular item in sorted array. In each step, the algorithm divides the array equally and match the middle item. If the key match, return the index. If key is less then middle, search left subarray. Else search right subarray.

Binary search uses divide and conquer strategy to search the item from the sorted array. The binary search eliminate half of the elements for each iteration. It requires sorted array and will not work for a un-sorted array like linear search.

The binary search algorithm can be implemented using the iterative method and recursive method. Write a program to implement Binary Search?

## source Code

```package com.dsacode.Algorithm.search;

import java.util.Arrays;

public class BinarySearch {
public static int BinSearch(int a[], int low, int high, int x){
int mid = (low+high)/2;
if(a[mid] == x)
return mid;
else if(a[mid] > x)
return BinSearch(a,low,mid-1,x);
else
return BinSearch(a,mid+1,high,x);
}

public static int Binarysearch(int a[], int x){
int low = 0, high = a.length -1;
int mid = 0;
while(low <= high){
mid = (low + high)/2;

if(a[mid] > x)
high = mid-1;
else if(a[mid] < x)
low = mid+1;
else
return mid;
}
return -1;
}

public static void main(String[] args) {
int[] array = {12, 55, 45, 11, 23, 20, 17, 24, 9};
System.out.println("Before Sort:" + Arrays.toString(array));
Arrays.sort(array);
System.out.println("After Sort:" + Arrays.toString(array));
int pos = -1;
if( (pos= Binarysearch(array,11)) == -1)
else
System.out.println("Found in " + (pos+1) + " Position!");

}
}```

## Output

```Before Sort: [12, 55, 45, 11, 23, 20, 17, 24, 9]
After Sort: [9, 11, 12, 17, 20, 23, 24, 45, 55]
Found in 2 Position!```