Linear Search in Java has always been the go-to method to find an element in an array. It searches each element of the array sequentially and is extremely easy to implement. However, the shortcomings of Linear Search are obvious when the array in question contains tens of thousands of elements. In such cases, the “divide and conquer” method implemented by Binary Search is a lot more efficient and preferable for programmers with time and space complexity in mind.

## Binary Search

In Binary Search, an array is repeatedly divided into two halves until the key (element that is being searched) is found. The division is virtual i.e. the integrity of the data is maintained. With every iteration, the middle value of the array is focused. If the value is equal to the key we are looking for, the loop or recursive function terminates. Otherwise, it keeps on looping. If the middle value is greater than the key, the function then focuses on the first half of the array and vice versa. This process is repeated until the key is found or the entire array has been iterated.## Difference Between Linear and Binary Search

Linear Search | Binary Search |
---|---|

Sequentially searches the array | Divides the array into two halves until the value is found |

Works with any array | Works only with sorted arrays |

Complexity is O(N) | Complexity is O(log2N) |

Can work on sorted and unsorted arrays | Can only be implemented on sorted arrays. |

Less complex to implement | More complex to implement |

## Binary Search Algorithm

The algorithm of Binary Search is given below.- Determine first and last points of the array. The points will be adjusted at each iteration as per the array and the key being searched.
- Iterate through the array and compare the middle value between your current first and last points. In the first iteration, the first and the last variable will be the same as the actual ones in the array.
- If the key is greater than the middle value, the index of that value will be stored in the new “First” variable.
- If the key is less than the middle value, the index of that value will be stored in the ‘Last’ variable.
- This condition is repeated until one of two conditions become true:
- Key is found.
- The entire array has been iterated.

## Iterative Binary Search

The code for Binary Search with an iterative method is given below.```
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
//Representing the Start and End Index After Division of Array
int start = 0;
int end = arr.length;
//Loop to Iterate Through the Array
for(int i = 0; iarr[n]){
start = n;
}
//If number to search for is greater than the arr value at index 'n'
else{
end = n;
}
}
//If number isn't found, return -1
return -1;
}
}
```

## Recursive Binary Search

The code for Binary using recursion is given below.```
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
//Base Case to Exit the Recursive Function
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
//If number is found at mean index of start and end
if(arr[n]==num)
return n;
//If number to search for is greater than the arr value at index 'n'
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
//If number to search for is greater than the arr value at index 'n'
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
```