Binary Search Implementation in Java Example

Binary search is one of the most important searching algorithm to know and understand for search functionality. In the below we are going to return the array position based on the searching number existence in the array, if it does not exist then we will return -1.

 

Binary search basically works this way,

1. Numbers should be sorted in the array before beginning with binary search.
2. Check the middle number with the number which need to be searched and finds whether the number matches or greater or lesser.
3. Based on this, again it takes only the particular side (from middle right or left based on point(2) and performs the same steps again until the number matches, if not matched then it returns -1).

 

Where as linear search works directly from beginning all the time so the Big O(1) if first matches and worst case Big O(N).

 

Pseudo-code for Binary Search:

Array = input array & x = number to search and return -1 if the array does not contain the searching number x.

Step 1: Have three variable namely p (initially 0),r(array length-1)

Step 2: Have a while loop and allow if only p<=r, if p>r then it will return -1.
(a) q = floor[(p+1)/2] to consider 2 if 2.5
(b) if array[q]==x return the position that is q.
(c) if array[q] > x then set the r as r=q-1;
(d) else set the p as p = q+1;
(e) repeat the same step until we get the position or -1 as a result.

 

Below are the sample binary search java program which implements the above pseudo-code.

Singly Linked List Algorithm Implementation Java Example

Before looking the below solution, please write your own program with the above pseudo-code only, which really helps a lot for clear understanding, feel free to write your comments if you stuck anywhere to help and make you understand better.

 

Binary Search Implementation in Java Example:

[java]

package in.javadomain;

public class BinarySearch {

public static void main(String[] args) {
System.out.println(getValuePosition(new int[]{2,4,5,8,90}, 8));
}

public static int getValuePosition(int [] inputArray, int numberToSearch){
int p=0;
int r = inputArray.length-1;

while(p<=r){ int q = (int) Math.floor((p+r)/2); if(inputArray[q]==numberToSearch){ return q; }else if(inputArray[q]>numberToSearch){
r = q-1;
}else{
p = q+1;
}
}
return -1;
}
}

[/java]

 

Reversing a string using Stack Implementation

Output:

[plain]
3

[/plain]

 

 

 

Recursive Binary Search Code Implementation:

 

You can call the below recursive binary search method from main like this to get the similar output using recursive mechanism

 

int[] inputArray = new int[]{2,4,5,8,90};int[] inputArray = new int[]{2,4,5,8,90}; System.out.println(recursiveBinarySearch(inputArray,0, inputArray.length-1,12));

public static int recursiveBinarySearch(int[] array, int startPosition, int endPosition, int numberToSearch){

int center = (startPosition+endPosition)/2;
if(startPosition>endPosition){
return -1;
}else if(array[center]==numberToSearch){
return center;
}else if(array[center]>numberToSearch){
endPosition = center-1;
return recursiveBinarySearch(array,startPosition,endPosition,numberToSearch);
}else if(array[center]<numberToSearch){
startPosition = center+1;
return recursiveBinarySearch(array,startPosition,endPosition,numberToSearch);
}
return center;

}