AppDividend
Latest Code Tutorials

# Java Binary Search Program | Binary Search In Java Example

We are going to learn about one of the fastest searching methods, which is the Binary Search. This searching method is also known as half-interval search, logarithm search, or binary chop. Always remember, this searching method works only on a sorted array or list. A binary search is used to search the key item from multiple items. Binary search is faster than a linear search.

## Java Binary Search

In the case of binary search, array elements must be in ascending order. If you have an unsorted array, you can sort the array using Arrays.sort(arr) method.

Binary Search works like the following.

Search the sorted array by repeatedly dividing the search interval in half.

Begin with the interval covering the whole array.

If a value of the search key is less than an element in the middle of the interval, narrow the interval to the lower half.

Otherwise, narrow it to the upper half. Repeatedly check until a value is found or an interval is empty.

## #Procedure

The standard procedure of this search is; first, we have to take a sorted array, and then we have to compare the target value with the middle value of the sorted array.

If a target value is less than the middle value, then we will eliminate the remaining halves ( right side of the middle value ), and we will continue searching with the selected halves.

Then we will again take the middle value of the selected halves (left subarray) and compare, again we have to eliminate by comparing, and we will do so until we get our target value.

## #Algorithm of Binary Search

```1.   [Define variables]
ST = LB, LAST= UB; //LB means Lower Bound, UB= Upper Bound
MID = (ST+LAST)/2; //Middle Value
2.   Repeat 3 and 4 DO ST <= LAST & DATA[MID] != ITEM
3.   If ITEM < DATA[MID] then
LAST = MID-1
If not
ST = MID+1
4.   Set MID = INT((ST + LAST)/2)
[LAST repeat to 2]
5.   If DATA[MID] == ITEM then
LOK = MID
If not
LOK = NULL
6.   Stop```

## #Understanding with an Example

Let’s assume a sorted array.

 Value 12 15 17 29 31 41 55 Index 0 1 2 3 4 5 6

Now let’s assume our target value T=17, which is at index 2. We will see how binary search will be applied in this case.

LB=0 and UB=6, so middle value will be: MID=(0+6)/2 =3, so our middle value is at position LOC= 3.

Pass1: Now, we will compare target value (T) with middle value (MID) as we can see T<MID, so we will eliminate the right subarray from index 3 to 6.

Pass2: Now, our middle value will be index 1 and target value T=17 as it is. Now we will compare MID with T, as T>MID so that we will eliminate left subarray.

Pass3: Now, our middle value and only remaining value is at index 2, that is 17. Also, we can see that our target value T is also 17. So, after comparing when we get that MID==T, we will stop and will return the location of the target value, which is LOC=2.

So, from the example, we can say that our target value is present at the index position.

## #Program of Binary Search In Java

See the below program.

```import java.util.*;

class Binary {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("\nEnter the length of the array:");
int len = sc.nextInt();
int[] arr = new int[len];
System.out.println("Enter the elements of the array:\n");
for (int i = 0; i < len; i++) {
arr[i] = sc.nextInt();
}
System.out.println("Enter the elements you want to search:\n");
int data = sc.nextInt();
int UB = len - 1, LB = 0;
int loc = BinarySearch(arr, LB, UB, data);
if (loc >= 0)
System.out.println("Target value is at index: " + loc);
else
}

public static int BinarySearch(int arr[], int LB, int UB, int data) {
int mid = (LB + UB) / 2;
int loc = -1;
while ((LB <= UB) && (arr[mid] != data)) {
if (data < arr[mid])
UB = mid - 1;
else
LB = mid + 1;
mid = (LB + UB) / 2;
if (data == arr[mid]) {
loc = mid;
break;
} else
loc = -1;
}
;
return loc;
}
}```

See the below output.

## #Time complexity

The time complexity of binary search we can write as follows.

```T(n) = T(n/2) + c
```

The above recurrence can be solved either using the Recurrence Tree method or Master method.

It falls in case II of Master Method and solution of the repetition will be following.

```Theta (log n)
```

## #Space Complexity

O(1) in case of iterative implementation. In the case of recursive implementation.

O(log n) recursion call stack space.

Finally, the Java Binary Search Program is over.

This site uses Akismet to reduce spam. Learn how your comment data is processed.