Tag Archives: Algorithm

Algorithm, Data Structure, Java

Binary Search Java Program

1 Comment

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 = 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

 

Java Program

[Sorting] Bubble Sort/ Sinking Sort Java Program

1 Comment

Bubble Sort also called Sinking Sort is a comparison sort algorithm where smaller or larger “bubble” elements move to top.

Complexity

Complexity of bubble sort is O(n2) in both average and worst case while O(n) in best case when elements are already sorted. Where n is number of elements.

Drawback

It will not be efficient in the case of a reverse-ordered collection or number of elements are high.

import java.util.Scanner;

public class BubbleSort {
public static void main(String []args) {
int n, c, d, swap;
//For User Input
Scanner in = new Scanner(System.in);

System.out.println("Input number of integers to sort");
n = in.nextInt();

int array[] = new int[n];

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

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

for (c = 0; c < ( n - 1 ); c++) {
for (d = 0; d < n - c - 1; d++) {
/* In case of descending order use < */ if (array[d] > array[d+1])
{
swap       = array[d];
array[d]   = array[d+1];
array[d+1] = swap;
}
}
}
System.out.println("Sorted list of numbers");

for (c = 0; c < n; c++)
System.out.println(array);
}
}

 

More

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