Java Code for Binary Search using array example

                        Binary Search searches the specified value (key) in a sorted array (Ascending) and returns the position. Let us see how the Binary Search algorithm works. In this search algorithm, the key is compared with the middle element of the array. If it matches, then the key is found at the middle of the array. If the key is less than the middle element, then the key should be found at left side of the middle element. If the key is greater than the middle element, then the  key should be found at the right side of the middle element. The search continues on either lower half or upper half  of the array.

Consider an array (A) having n elements. Key is the value to be searched. low ->1, high-> n. Now find mid -> (low+high) /2. If Key==A[mid], then position -> mid, if Key<A[mid], then high->mid-1, if Key>A[mid], then low->mid+1, else not found

For Example let us take the numbers  77,33,22,55,34 and find the position of   55 in the list. Sorted list will be 22,33,34,55,77. Middle position is 3 and the  element is 34. Now 55 is compared with 34 and  55 is greater than 34. So the key will be on right side of 34. Now the search continues with elements 55 & 77, and the middle position is 4, now key 55 is compared with 55. Both are equal, so the key is found at 4th position.

In two ways, we can do binary search. One is using the Collections.binarySearch(List list, Object key)   OR We can write our own function as given below

 

package net.javaonline;

import java.util.Arrays;
import java.util.Scanner;

public class BinarySearch {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("Enter howmany numbers are in in the array ");
		int n = sc.nextInt();
		int[] arr = new int[n];
		int key = 0;
		System.out.println("Enter " + n + " numbers");
		for (int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
		}
		System.out
				.print("Enter any number to search in array using binary search ");
		key = sc.nextInt();
		System.out.print("Given List of  Numbers : ");
		for (int element : arr)
			System.out.print(element+ " ");
		Arrays.sort(arr);
		System.out.print("List of Numbers after Sorting");
		for (int element : arr)
			System.out.print(element+ " ");
		System.out.println(" ");
		int pos = binsearch(key, arr);
		if (pos == -1)
			System.out.println("Given Number " + key + " Not Found");
		else
			System.out.println("Given Number " + key + " Found at Position "
					+ (pos + 1));
	}

	// Binary Search algorithm
	public static int binsearch(int searchValue, int[] searchList) {
		int high = searchList.length - 1;
		int low = 0;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (searchValue > searchList[mid])
				low = mid + 1;
			else if (searchValue < searchList[mid])
				high = mid - 1;
			else
				return mid;
		}
		return -1;
	}


}

Output:

binary search

 

Leave a Reply