Binary Search Java Program


Binary search, also known as half-interval search,binary chop or logarithmic search.

How it Works?

Binary search works on sorted arrays values. Binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than or greater
than the middle element, the search continues in the lower or upper half of the array, respectively, eliminating the other half from consideration.If the search ends with the remaining half being empty, the target is not in the array.

Time and Space Complexity?

Binary search runs in at worst logarithmic time, making O(log n) comparisons and takes constant (O(1)) space.

where n is the number of elements in the array, the O is Big O notation, and log is the logarithm.

Java API  for Binary Search

Java Arrays class also provide api’s for Binary Search. You can use as below

import java.util.Arrays;

public class BinarySearchByJavaAPI {

	public static void main(String[] args) {
		char characters[] = { 'l', 'm', 'n', 'p', 'q<span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>' };

	    System.out.println(Arrays.binarySearch(characters, 'a'));
	    System.out.println(Arrays.binarySearch(characters, 'p'));

	}

}

Java Program for Binary Search

import java.util.Scanner;

class BinarySearch
{
  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 + " sorted 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 ><span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span> last )
      System.out.println(search + " is not present in the list.\n");
  }
}

More Info

For more Algorithms and Java Programing Test questions and sample code follow below links

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s