AppDividend
Latest Code Tutorials

Java Binary Search Program | Binary Search In Java Example

0

Java Binary Search Program | Binary Search In Java Example is today’s topic. We are going to learn about one of the fastest searching methods, which are 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. 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 lower half.

Otherwise, narrow it to 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, that 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
      System.out.println("Target value not found");
  }

  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.

 

Java Binary Search Program

#Time complexity

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

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

Above recurrence can be solved either using 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 | Binary Search In Java Example is over.

Leave A Reply

Your email address will not be published.

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