Binary Search In Java

Chapter: Miscellaneous Last Updated: 19-07-2016 03:15:40 UTC

Program:

            /* ............... START ............... */
                
import java.util.Scanner;

public class JavaBinarySearch {
	public static void main(String args[]) {
		int c, first, last, middle, n, search, array[];

		Scanner in = new Scanner(System.in);
		System.out.println("Enter number of elements");
		n = in.nextInt();
		array = new int[n];

		System.out.println("Enter " + n + " integers");

		for (c = 0; c < n; c++)
			array[c] = in.nextInt();

		System.out.println("Enter value to find");
		search = in.nextInt();

		first = 0;
		last = n - 1;
		middle = (first + last) / 2;

		while (first <= last) {
			if (array[middle] < search)
				first = middle + 1;
			else if (array[middle] == search) {
				System.out.println(search + " found at location " + (middle + 1) + ".");
				break;
			} else
				last = middle - 1;

			middle = (first + last) / 2;
		}
		if (first > last)
			System.out.println(search + " is not present in the list.\n");
	}
}

                /* ............... END ............... */
        

Output

Enter number of elements
5
Enter 5 integers
10
46
34
24
2
Enter value to find
34
34 found at location 3.

Notes:

  • A binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array.
  • The algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element.
  • Every iteration eliminates half of the remaining possibilities. This makes binary searches very efficient - even for large collections.
  • Worst case performance: O(log n).
  • Best case performance: O(1).

Tags

Binary Search, Java

Similar Programs Chapter Last Updated
Data Types In Java Miscellaneous 09-06-2018
Java Program To Find Largest Element Of Array Miscellaneous 21-09-2017
Java Program To Check Whether Number Is Prime Or Not Miscellaneous 08-09-2017
Java Program To Find Power Of Number Using For Loop Miscellaneous 29-08-2017
Java Program To Find LCM Of Two Numbers Miscellaneous 29-08-2017
Java Program To Find GCD Of Two Numbers Miscellaneous 29-08-2017
Java Program To Check Whether An Alphabet Is Vowel Or Consonant Miscellaneous 25-08-2017
Java Program To Find ASCII Value Of Character Miscellaneous 25-08-2017
Java Object HashCode Method Miscellaneous 02-08-2017
Java Builder Design Pattern Example Miscellaneous 06-06-2017
Java Factory Design Pattern Example Miscellaneous 06-06-2017
Java Program To Print ASCII Values Miscellaneous 06-04-2017
Java Program To Find HCF LCM Of Two Numbers Miscellaneous 22-09-2018
Java String Array Iteration Miscellaneous 31-03-2017
Java Array Size Miscellaneous 30-03-2017
Java Integer toString Miscellaneous 30-03-2017
Java Sort Array Using Arrays.sort() Miscellaneous 28-03-2017
Java Print Array Using Arrays.toString Miscellaneous 28-03-2017
Java Nested Interface Miscellaneous 25-03-2017
Java Static Nested Class Miscellaneous 25-03-2017
Packages In Java Miscellaneous 24-03-2017
Java Strictfp Keyword Miscellaneous 24-03-2017
Java Call By Reference Miscellaneous 23-03-2017
Java Call By Value Miscellaneous 23-03-2017
Java Unboxing Example Miscellaneous 23-03-2017
Java Autoboxing Example Miscellaneous 23-03-2017
Java Format Currency Miscellaneous 15-02-2017
Java String To BigDecimal Conversion Miscellaneous 15-02-2017
Java Program To Convert Arraylist To Array Miscellaneous 13-02-2017
Java Array Creation And Initialize Miscellaneous 13-02-2017

1 2 3 4 5