Java – Binary Search

Binary Search:

• Another searching algorithm to search for an element in array.
• Binary search can apply only on sorted array
• In this searching process, we find the mid element and compare with element to be searched.
• If mid element matches with element, returns mid location as element location.
• If the searching element less than mid element, search continues in the left side array of mid location.
• If the element is greater than mid element, searching will be in right array.

import java.util.Scanner;
class Main
{
	static int arr[ ];
	static boolean found=false;
	public static void main(String[] args) 
	{
		Scanner scan = new Scanner(System.in);
		System.out.print("Enter array size : ");
		int n = scan.nextInt();
		arr = new int[n];

		System.out.println("Enter "+n+" elements : ");
		for (int i=0 ; i<n ; i++)
		{
			arr[i] = scan.nextInt();
		}

		System.out.print("Enter element to be searched : ");
		int key = scan.nextInt();

		int low=0;
		int high=arr.length-1;
		while(low<=high)
		{
			int mid = (low+high)/2;
			if(key<arr[mid])
			{
				high = mid-1;
			}
			else if(key>arr[mid])
			{
				low = mid+1;
			}
			else if(key == arr[mid])
			{
				System.out.println("Element found @ location : " + mid);
				found = true;
				break;
			}
		}
		
		if(!found)
			System.out.println("Element not found");
	}
}