Table of Contents

Binary search is used to find the location of a value in a sorted array. It is proven to be the fastest way to find the value.
Algorithm
The program starts from the middle of the array and checks if it is a match with the value. If not, we want to check whether the mid value is greater or less than the search value. If less, then we can ignore/cut off all the values greater than or equal to the mid value and vice versa if greater. We then repeat the process on the section of the array. This goes on until we either find a match or when there is no way to continue dividing the array.
Step by Step
The program undergoes a series of steps:
 Finds the middle and checks if it is equal to the value.
 If it is a match, the program returns the place of the value.
 If not… step 2.
 Checks if the value is less than or greater than the middle.
 If it is less than the middle:
 The high is moved to one less than middle.
 A new middle is found between the low and the high.
 Return to the original step one.
 If it is greater than the middle:
 The low is moved to one greater than the middle.
 A new middle is found between the low and the high.
 Return to the original step one.
 If it is less than the middle:
Visual Binary Search
Code
public static int binarySearch (int[] x, int value) { int low = 0, high = x.length  1, mid; while (low <= high) { mid = (low + high) / 2; if (x[mid] > value) { high = mid  1; } else if (x[mid] < value) { low = mid + 1; } else { return mid; } } return 1; }
The method returns a 1 if the value is not found in the array because an array cannot have a negative index.
Runtime
Best case
The best case scenario is when the value you are searching for is in the middle of the array, which will have a runtime of O(1).
Worst case
The worst case is when the value being searched is not in the array. the method will run log_{2}n times (see).
Recursive
Code for doing Binary Search recursively.
Code
public static void main(String[] args) {
int[] x = {2,4,6,7};
System.out.print(binary(x, 6));
}
public static int binary(int[] x, int ans){
return binary(x, x.length1, 0, ans);
}
public static int binary(int[] x, int high, int low, int ans){
int mid = (high + low) / 2;
if( x[mid] == ans){
return mid;
}
else if(high < low){
return 1;
}
else if(x[mid] > ans){
return binary(x, mid  1, low, ans);
}
else{
return binary(x, high, mid + 1, ans);
}
}
Note: method overloading is used to create two binary methods.