by BehindJava

How to implement Binary Search Algorithm in Data Structures using Java

Home » datastructures » How to implement Binary Search Algorithm in Data Structures using Java

In this blog, we are going to learn about implementing the Binary Search Algorithm in Data Structures using Java.

Binary Search

  • The binary search is the standard algorithm for searching through a sorted sequence.
  • It is much more efficient than the sequential search, but it does require that the elements be in order.
  • It repeatedly divides the sequence in two, each time restricting the search to the half that would
  • Contains the element.
  • You might use the binary search to look up a word in a dictionary.

Algorithm

(Binary search) BINARY(DATA, LB, UB, ITEM, LOC) Here DATA is a sorted array with lower bound LB and upper bound UB, and ITEM is a given item of information. The variables BEG, END and MID denote, resp., the beginning, end, and middle locations of a segment of elements of DATA. The algo finds the location LOC of ITEM in DATA or sets LOC = NULL.

  1. [Initialize segment variables.] Set BEG := LB, END := UB and MID := INT((BEG + END) / 2).
  2. Repeat steps 3 and 4 while BEG <= END and DATA[MID] != ITEM.
  3. If ITEM < DATA[MID], then: Set END := MID – 1. Else: Set BEG := MID + 1.\ [End of If.]
  4. Set MID := INT((BEG + END)/2). [End of Step 2 loop.]
  5. If DATA[MID] = ITEM, then: Set LOC := MID. Else: Set LOC := NULL. [End of If.]
  6. Exit

Performance

  • The binary search runs in O(lg n) time.
  • This means that, on average, the running time is proportional to the logarithm of the number of elements in the array.
  • So if it takes an average of T milliseconds to run on an array of n elements, then will take an average of 2T milliseconds to run on an array of n2 elements.
  • For example, if it takes 3 ms to search 10,000 elements, then it should take about 6 ms to search 100,000,000 elements!
  • Each iteration of the loop searches a subarray that is less than half as long as the subarray on the previous iteration.
  • Thus the total number of iterations is no more than the number of times that the length n can be divided by 2. That number is lg n.
  • And the total running time is roughly proportional to the number of iterations that the loop makes.

Binary Search in Java

public class BehindJava {

	public static void main(String[] args) {
		int[] intArray = { -22, -15, 1, 7, 20, 35, 55 };

		System.out.println("Found at Location:"+iterativeBinarySearch(intArray, -15));
		System.out.println("Found at Location:"+iterativeBinarySearch(intArray, 35));
		System.out.println("Found at Location:"+iterativeBinarySearch(intArray, 8888));
		System.out.println("Found at Location:"+iterativeBinarySearch(intArray, 1));

		System.out.println("Found at Location:"+recursiveBinarySearch(intArray, -15));
		System.out.println("Found at Location:"+recursiveBinarySearch(intArray, 35));
		System.out.println("Found at Location:"+recursiveBinarySearch(intArray, 8888));
		System.out.println("Found at Location:"+recursiveBinarySearch(intArray, 1));
	}

	public static int iterativeBinarySearch(int[] input, int value) {
		int start = 0;
		int end = input.length;

		while (start < end) {
			int midpoint = (start + end) / 2;
			System.out.println("midpoint = " + midpoint);
			if (input[midpoint] == value) {
				return midpoint;
			} else if (input[midpoint] < value) {
				start = midpoint + 1;
			} else {
				end = midpoint;
			}
		}

		return -1;
	}

	public static int recursiveBinarySearch(int[] input, int value) {
		return recursiveBinarySearch(input, 0, input.length, value);
	}

	public static int recursiveBinarySearch(int[] input, int start, int end, int value) {
		if (start >= end) {
			return -1;
		}

		int midpoint = (start + end) / 2;
		System.out.println("midpoint = " + midpoint);

		if (input[midpoint] == value) {
			return midpoint;
		} else if (input[midpoint] < value) {
			return recursiveBinarySearch(input, midpoint + 1, end, value);
		} else {
			return recursiveBinarySearch(input, start, midpoint, value);
		}
	}
}

Output:

midpoint = 3
midpoint = 1
Found at Location:1
midpoint = 3
midpoint = 5
Found at Location:5
midpoint = 3
midpoint = 5
midpoint = 6
Found at Location:-1
midpoint = 3
midpoint = 1
midpoint = 2
Found at Location:2
midpoint = 3
midpoint = 1
Found at Location:1
midpoint = 3
midpoint = 5
Found at Location:5
midpoint = 3
midpoint = 5
midpoint = 6
Found at Location:-1
midpoint = 3
midpoint = 1
midpoint = 2
Found at Location:2

Comparison between Binary Search and Linear Search

Binary search operates on sorted lists Linear search can operate on unsorted Lists as well.
Binary search is complex as compared to linear search. Linear search is simple and straight forward to implement than the Binary Search.
Binary Search is considered to be a more efficient method that could be used with large lists. But, Linear search is too slow to be used with large lists due to its O(n) average case performance.
Number of comparisons are less More number of comparisons are required if the items are present in the later part of the array or its elements are more.
Works well with arrays and not on linked lists. Works with arrays and linked lists.