Monday, 18 February 2019

Queue Implementation in Java Using Array

In this post we’ll see an implementation of Queue in Java using array. Queue can also be implemented using Linked list.

Queue data structure

A queue is a First In First Out (FIFO) data structure where the first item inserted is the first to be removed. In a queue items are inserted at the rear and removed from the front of the queue.

When you implement queue using array, fact that an array once defined has a fixed size causes problem in the queue implementation. When items are inserted in a queue and later removed that creates a gap, to fill that gap you can shift the remaining elements to fill that space but that is an expensive operation. Another option is to implement a circular queue where front and rear start pointing to the beginning of the array once maximum size is reached.

Following image shows how circular queue works.

Queue implementation in Java

Operations in a Queue

Mainly following three operations are implemented for a Queue-

  1. insert- To insert an item at the rear of the queue.
  2. remove- To remove an item from the front of the queue.
  3. peek- Read value from the front of the queue without removing it.

Java program for Queue

public class Queue {
    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int currentSize;
    public Queue(int size){
        this.maxSize = size;
        this.queueArray = new int[size];
        front = 0;
        rear = -1;
        currentSize = 0;
    }
    public void insert(int item){
        //check if queue is already full
        if(isQueueFull()){
            System.out.println("Queue is full!");
            return;
        }
        // for wrapping the queue in case 
        //  max size has reached
        if(rear == maxSize - 1){
            rear = -1;
        }
        // increment rear then insert item
        queueArray[++rear] = item;
        currentSize++;
        System.out.println("Added to queue" + item);
    }
    
    public int remove(){
        //check if queue is empty
        if(isQueueEmpty()){
            throw new RuntimeException("Queue is empty");
        }
        //System.out.println("front= " + front + " maxSize= "+maxSize);
        // retrieve item then increment
        int temp = queueArray[front++];
        if(front == maxSize){
            front = 0;
        }
        currentSize--;
        return temp;
    }
    public int peek(){
        return queueArray[front];
    }
    public boolean isQueueFull(){
        return (maxSize == currentSize);
    }
    
    public boolean isQueueEmpty(){
        return (currentSize == 0);
    }
    public static void main(String[] args) {
        Queue queue = new Queue(10);
        queue.insert(2);
        queue.insert(3);
        System.out.println("Item removed- " + queue.remove());
        System.out.println("Item removed- " + queue.remove());
        queue.insert(5);    
        System.out.println("Item removed- " + queue.remove());
        
    }
}

Output

Added to queue2
Added to queue3
Item removed- 2
Item removed- 3
Added to queue5
Item removed- 5

As you can see from the image as well as in the code both front and rear move towards the higher index and there are insertions and removals. That will result in Queue becoming full and not able to take new items even if there is space created in the front because of the removals, if not implemented as circular queue.

To keep track of the current size there is a field currentSize which is incremented with each insertion and decremented with each removal. If maxSize == currentSize that means queue is actually full otherwise even if maxSize is reached there is space created at the front which can be used by wrapping the rear to start from the beginning. Same way front can also be wrapped to start from the beginning once it reaches maxSize.

Performance of queue

In queue items can be inserted and removed in O(1) time.

That's all for this topic Queue Implementation in Java Using Array. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Linked List Implementation Java Program
  2. Stack Implementation in Java Using Array
  3. Insertion Sort Program in Java
  4. Producer-Consumer Java Program Using ArrayBlockingQueue
  5. Converting Numbers to Words - Java Program

You may also like -

>>>Go to Java Programs Page

Sunday, 17 February 2019

Difference Between Two Dates in Java

In this post we’ll see how to calculate difference between two dates in Java using SimpleDateFormat and using the new date and time API in Java 8.

Difference between two dates using SimpleDateFormat

Before Java 8 you could calculate difference between two dates manually using SimpleDateFormat.

public class DateDiff {
 public static void main(String[] args) { 
  try {
   dateDifference("28/02/2016 13:15:55", "01/03/2016 17:18:14", "dd/MM/yyyy HH:mm:ss");
  } catch (ParseException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
 }
 
 private static void dateDifference(String date1, String date2, String pattern) throws ParseException{
  SimpleDateFormat sdf = new SimpleDateFormat(pattern);
  Date d1 = sdf.parse(date1);
  Date d2 = sdf.parse(date2);
  long diffInMillis = d2.getTime() - d1.getTime();
  long dateDiffInDays = TimeUnit.DAYS.convert(diffInMillis, TimeUnit.MILLISECONDS);

  long dateDiffInHours = TimeUnit.HOURS.convert(diffInMillis - (dateDiffInDays * 24 * 60 * 60 * 1000), TimeUnit.MILLISECONDS);

  long dateDiffInMinutes = TimeUnit.MINUTES.convert(diffInMillis - (dateDiffInDays * 24 * 60 * 60 * 1000) -(dateDiffInHours * 60 * 60 * 1000), TimeUnit.MILLISECONDS);

  long dateDiffInSeconds = TimeUnit.SECONDS.convert(diffInMillis - (dateDiffInDays * 24 * 60 * 60 * 1000) - (dateDiffInHours * 60 * 60 * 1000) - (dateDiffInMinutes * 60 * 1000), TimeUnit.MILLISECONDS);

  System.out.println(dateDiffInDays + " day(s) " + dateDiffInHours + " Hour(s) " + dateDiffInMinutes + " Minute(s) " + dateDiffInSeconds + " Second(s)");
 }
}

Output

2 day(s) 4 Hour(s) 2 Minute(s) 19 Second(s)

Difference between two dates in Java 8

Java 8 onward you can use you can use new date and time API classes Period and Duration to find difference between two dates.

  • Period class is used to model amount of time in terms of years, months and days.
  • Duration class is used to model amount of time in terms of seconds and nanoseconds.

Using these two classes you can calculate difference between two dates in terms of years, months, days along with hours, minutes, seconds (for time component).

Difference between dates - Java code

import java.time.Duration;
import java.time.LocalDate;
import java.time.LocalDateTime;
import java.time.LocalTime;
import java.time.Period;

public class DateDiff {
 public static void main(String[] args) {
  LocalDateTime dateTime1 = LocalDateTime.of(2016, 8, 28, 13, 15, 55);
  LocalDateTime dateTime2 = LocalDateTime.of(2016, 8, 29, 17, 18, 14);

  getPeriod(dateTime1.toLocalDate(), dateTime2.toLocalDate());
  getTime(dateTime1.toLocalTime(), dateTime2.toLocalTime());
 }
 
 /**
  * 
  * @param date1
  * @param date2
  */
 private static void getPeriod(LocalDate date1, LocalDate date2){
  Period p = Period.between(date1, date2);
  System.out.println("Year " + p.getYears());
  System.out.println("Months " + p.getMonths());
  System.out.println("Days " + p.getDays());   
 }
 /**
  *   
  * @param time1
  * @param time2
  */
 private static void getTime(LocalTime time1, LocalTime time2){
   
  Duration d = Duration.between(time1, time2);
  long seconds = d.getSeconds();
  //System.out.println("seconds " + seconds);
  // Calculating hours
  System.out.println("Hours " + d.toHours());
  // Calculating Minutes
  System.out.println("Minutes " + ((seconds % 3600)/60));
  // Calculating Seconds
  System.out.println("Seconds " + (seconds % 60));

 }
}

Output

Year 0
Months 0
Days 1
Hours 4
Minutes 2
Seconds 19

Running it with another set of dates -

LocalDateTime dateTime1 = LocalDateTime.of(2016, 8, 28, 13, 15, 55);
LocalDateTime dateTime2 = LocalDateTime.of(2017, 10, 5, 15, 12, 59);

Output

Year 1
Months 1
Days 7
Hours 1
Minutes 57
Seconds 4

That's all for this topic Difference Between Two Dates in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How to convert date and time between different time-zones in Java
  2. How to Format Time in AM-PM Format - Java Program
  3. How to format date in Java using SimpleDateFormat
  4. How to convert Date to String in Java
  5. How to find last modified date of a file in Java

You may also like -

>>>Go to Java Programs Page

Friday, 15 February 2019

Stack Implementation in Java Using Linked List

In this post we’ll see an implementation of Stack in Java using Linked list. Stack can also be implemented using array but that has one drawback that the stack size is fixed in that case.

Stack data structure

A stack is a Last In First Out (LIFO) data structure. In a stack items are both inserted and removed from the top and you have access to a single data item; that is the last item inserted. Once that is retrieved then only you can access the next item.

Following image shows the items in a Stack.

Java program for stack

Operations in a Stack

Mainly following three operations are implemented for a Stack-

  1. push- To insert an item on the stack.
  2. pop- To remove an item from the top of the stack.
  3. peek- Read value from the top of the stack without removing it.

Java program for Stack using Linked list

For representing nodes of the linked list a separate class (private class Node in the program) is used which apart from the data also holds a reference to itself.

There is also one reference top which always points to the first node of the Linked list (top of the stack).

For push operation new nodes are inserted in the beginning of the Linked list and the top references the new node.

For pop operation first node in the Linked list is removed and the top starts referencing to the next node.

public class LinkedListStack {
    //Reference for the top of the stack
    Node top;
    public LinkedListStack(){
        top = null;
    }
    //Class representing each node
    private class Node{
        //data
        int i;
 //ref to next node
        Node next;
        Node(int i){
            this.i = i;
        }
        public void displayData(){
            System.out.println("i= " + i);
        }
    }
    
    public void insertNode(int i){
        //Create a new node
        Node newNode = new Node(i);
        // current top is pushed down
        newNode.next = top;
        // newly inserted node is referenced by top
        top = newNode;
    }
    
    public int removeNode(){        
        Node temp = top;
        // Next item in the stack is referenced by top
        top = top.next;
        return temp.i;
    }
    
    public int nodeData(){
        return top.i;
    }
    
    public boolean isEmpty(){
        return top == null;
    }
    
    public void push(int item){
        insertNode(item);
    }
    public int pop(){
        // If no item is inserted
        if(isEmpty()){
            throw new RuntimeException("Stack is Empty");
        }
        return removeNode();
    }
    
    public int peek(){
        // If no item is inserted
        if(isEmpty()){
            throw new RuntimeException("Stack is Empty");
        }
        return nodeData();
    }
    
    public void displayStack(){
        // start from the top
        Node current = top;
        // traverse the list
        while(current != null){
            current.displayData();
            current = current.next;
        }
    }
    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        System.out.println("Item peeked- " + stack.peek());
        System.out.println("Items in stack--");
        stack.displayStack();
        System.out.println("Item popped- " + stack.pop());
        System.out.println("Item popped- " + stack.pop());
        System.out.println("Item peeked- " + stack.peek());
        System.out.println("Items in stack--");
        stack.displayStack();
    }
}

Output

Item peeked- 40
Items in stack--
i= 40
i= 30
i= 20
i= 10
Item popped- 40
Item popped- 30
Item peeked- 20
Items in stack--
i= 20
i= 10

That's all for this topic Stack Implementation in Java Using Linked List. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Counting Sort Program in Java
  2. How to Create Your Own BlockingQueue - Java Program
  3. How to Find Common Elements Between Two Arrays - Java Program
  4. Find Duplicate Characters in a String With Repetition Count - Java Program
  5. Displaying Prime Numbers - Java Program

You may also like -

>>>Go to Java Programs Page

Stack Implementation in Java Using Array

In this post we’ll see an implementation of Stack in Java using array. Stack can also be implemented using Linked list.

Stack data structure

A stack is a Last In First Out (LIFO) data structure. In a stack items are both inserted and removed from the top and you have access to a single data item; that is the last item inserted. Once that is retrieved then only you can access the next item.

Following image shows the items in a Stack.

Java program for stack

Operations in a Stack

Mainly following three operations are implemented for a Stack-

  1. push- To insert an item on the stack.
  2. pop- To remove an item from the top of the stack.
  3. peek- Read value from the top of the stack without removing it.

Java program for Stack

public class Stack {
    private int maxSize;
    private int[] stackArray;
    private int top;
    Stack(int max){
        this.maxSize = max;
        stackArray = new int[maxSize];
        top = -1;
    }
    
    public void push(int item){
        if(top >= maxSize - 1){
            System.out.println("Stack already full..");
            return;
        }
        // increment top then insert item
        stackArray[++top] = item;
    }
    
    public int pop(){
        if(top < 0){
            throw new RuntimeException("Stack is Empty");
        }
        // retrieve item then decrement
        return stackArray[top--];
    }
    
    public int peek(){
        // return top item value
        return stackArray[top];
    }
    
    public boolean isEmpty(){
        return (top < 0);
    }
    
    public boolean isFull(){
        return (top == maxSize - 1);
    }
    
    public static void main(String[] args) {
        Stack stack = new Stack(20);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println("Item popped- " + stack.pop());
        System.out.println("Item popped- " + stack.pop());
        while(!stack.isEmpty()){
            System.out.println("Item popped- " + stack.pop());
        }
    }
}

Output

Item popped- 5
Item peeked- 4
Item popped- 4
Item popped- 3
Item popped- 2
Item popped- 1

Performance of stack

In stack items can be inserted and removed in O(1) time.

That's all for this topic Stack Implementation in Java Using Array. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Linked List Implementation Java Program
  2. Binary Search Program in Java
  3. Heap Sort Program in Java
  4. Check Whether Given String/Number is a Palindrome or Not - Java Program
  5. How to Run javap Programmatically From Java Program

You may also like -

>>>Go to Java Programs Page

Wednesday, 13 February 2019

Linked List Implementation Java Program

In this post we’ll see an implementation of Linked List in Java. Operations covered in this singly Linked List implementation are-

  1. Insert element at the beginning of a Linked List.
  2. Insert element at the last.
  3. Get node’s values by position.
  4. Delete node by position.
  5. Traverse linked list displaying values for all the nodes.

Linked List data structure

Linked list data structure though linear in nature doesn’t store its node in contiguous memory location like array. In Linked list nodes are linked by each node holding reference to the next node.

Following image shows the nodes in the Linked List and how nodes are linked.

Linked list implementation in Java

Java program for Linked List

For representing nodes of the linked list a separate class is used which apart from the data also holds a reference to itself.

class Node{
 //data
 int i;
 String str;
 // Reference to next node
 Node next;
}

Java implementation of linked list given here is a double ended list where we have two references head and tail; head always points to the first node and the tail is a reference to the last node.

Insertion in linked list

For insertion there are three scenarios insert at the beginning, insert at the end and insert at the given index.

1- Inserting at the beginning has two scenarios.

If it is the first node then both head and tail should point to it.

If nodes already exist then the inserted node should reference the current first node and head should start pointing to the inserted node.

public void insertFirst(int i, String str){
 //Create a new node
 Node newNode = new Node(i, str);
 if(isEmpty()){
  tail = newNode;
 }
 newNode.next = head;
 head = newNode;
 size++;
}

Note here that size variable is used to store the current size of the List.

2- Inserting at the end has two scenarios.

If it is the first node then both head and tail should point to it.

If nodes already exist then the current last node should reference the inserted node and tail should start pointing to the inserted node.

public void insertLast(int i, String str){
 Node newNode = new Node(i, str);
 if(isEmpty()){
  head = newNode;
 }else{
  tail.next = newNode;
 }
 tail = newNode;
 size++;
}
3- Inserting at the given index has three scenarios.

If inserting at index 0 that is equivalent to insertFirst.

If inserting at index when (index == size) that is equivalent to insertLast.

Otherwise traverse to the node currently at the given index and change the references so that the new node starts referencing the current node and the node which was previously referencing the current node should start referencing the new node.

linked list insertion java
public void insertAtIndex(int i, String str, int index){
    if(!isValidIndex(index)){
        throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
    }
    Node newNode = new Node(i, str);
    Node current = head;
    Node temp = head;
    //insert at the start
    if(index == 0){
        insertFirst(i, str);
    }
    // insert at last
    else if(index == size){
        insertLast(i, str);
    }else{
        for(int j = 0; j < index && current.next != null; j++){
            temp = current;
            current = current.next;
        }
        newNode.next = current;
        temp.next = newNode;
    }
    size++;    
}

Linked List traversal

For Linked list traversal from start to end you need to start from head and then move sequentially unless the next node reference is not null.

// Method to traverse and display all nodes
public void displayList(){
 Node current = head;
 while(current != null){
  current.displayData();
  current = current.next;
 }
}

To get element at a given index traverse to the node currently at that index and return that node.

public Node get(int index){
    if(!isValidIndex(index)){
        throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
    }
    Node current = head;
    for(int j = 0; j < index; j++){
        current = current.next;
    }
    return current;        
}

Deleting node in Linked List

For deletion there are three scenarios-

  • Delete first node
  • Delete last node
  • Delete node at given index

1- If you are deleting the first node then in your Linked list Java program what you need to do is to change the head reference so that it starts referencing the next node.

public void removeFirst(){
 Node first = head;
 if(first == null){
  throw new RuntimeException("Element not found..");
 }
 Node next = first.next;
 // dereference
 first.next = null;
 head = next;
 // If no node left after deleting node
 if(head == null){
  tail = null;
 }
 // if only one node left
 else if(head.next == null){
  tail = next;
 }
 size--;
}

2- If you are deleting the last node then change the reference for tail so that it starts referencing the previous node. Since it is a singly linked list implementation so you need to start from the first node and traverse the list till the end.

public void removeLast(){
 Node last = tail;
 if(last == null){
  throw new RuntimeException("Element not found..");
 }
 if(head == tail){
  removeFirst();
 }else{
  Node current = head;
  Node temp = head;
  while(current != last){
   temp = current;
   current = current.next;
  }
  tail = temp;
  tail.next = null;
  if(tail == null){
   head = null;
  }
 }
 size--;
}
3- Deleting node at the given index has three scenarios.

If deleting node at index 0 that is equivalent to removeFirst.

If deleting node at index when (index == size) that is equivalent to removeLast.

Otherwise traverse to the node at the given index and change the references so that the node on the left of the node to be deleted starts referencing the node on the right of the node to be deleted.

public void removeAtIndex(int index){
    Node current = head;
    Node temp = head;
    if(!isValidIndex(index)){
        throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
    }
    //insert at the start
    if(index == 0){
        removeFirst();
    }
    // insert at last
    else if(index == size){
        removeLast();
    }else{
        for(int j = 0; j < index && current.next != null; j++){
            temp = current;
            current = current.next;
        }
        temp.next = current.next;
        current.next = null;
    }
    size--;
}

Linked List implementation in Java – Full Program

class Node{
    //data
    int i;
    String str;
    // Reference to next node
    Node next;
    
    public Node(int i, String str){
        this.i = i;
        this.str = str;
        this.next = null;
    }
    public void displayData(){
        System.out.println("i= " + i + " str= " +str);
    }
}

public class LinkedList {
    private Node head;
    private Node tail;
    private int size = 0;
    public LinkedList(){
        head = null;
        tail = null;
    }
    public boolean isEmpty(){
        return head == null;
    }
    
    public void insertFirst(int i, String str){
        //Create a new node
        Node newNode = new Node(i, str);
        if(isEmpty()){
            tail = newNode;
        }
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    public void insertLast(int i, String str){
        Node newNode = new Node(i, str);
        if(isEmpty()){
            head = newNode;
        }else{
            tail.next = newNode;
        }
        tail = newNode;
        size++;
    }
    
    public void insertAtIndex(int i, String str, int index){
        if(!isValidIndex(index)){
            throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
        }
        Node newNode = new Node(i, str);
        Node current = head;
        Node temp = head;
        //insert at the start
        if(index == 0){
            insertFirst(i, str);
        }
        // insert at last
        else if(index == size){
            insertLast(i, str);
        }else{
            for(int j = 0; j < index && current.next != null; j++){
                temp = current;
                current = current.next;
            }
            newNode.next = current;
            temp.next = newNode;
        }
        size++;    
    }
    
    public Node get(int index){
        if(!isValidIndex(index)){
            throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
        }
        Node current = head;
        for(int j = 0; j < index; j++){
            current = current.next;
        }
        return current;        
    }
    
    // Method to traverse and display all nodes
    public void displayList(){
        Node current = head;
        while(current != null){
            current.displayData();
            current = current.next;
        }
    }
    
    public void removeFirst(){
        Node first = head;
        if(first == null){
            throw new RuntimeException("Element not found..");
        }
        Node next = first.next;
        // dereference
        first.next = null;
        head = next;
        // If no node left after deleting node
        if(head == null){
            tail = null;
        }
        // if only one node left
        else if(head.next == null){
            tail = next;
        }
        size--;
    }
    
    public void removeLast(){
        Node last = tail;
        if(last == null){
            throw new RuntimeException("Element not found..");
        }
        if(head == tail){
            removeFirst();
        }else{
            Node current = head;
            Node temp = head;
            while(current != last){
                temp = current;
                current = current.next;
            }
            tail = temp;
            tail.next = null;
            if(tail == null){
                head = null;
            }
        }
        size--;
    }
    
    public void removeAtIndex(int index){
        Node current = head;
        Node temp = head;
        if(!isValidIndex(index)){
            throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
        }
        //insert at the start
        if(index == 0){
            removeFirst();
        }
        // insert at last
        else if(index == size){
            removeLast();
        }else{
            for(int j = 0; j < index && current.next != null; j++){
                temp = current;
                current = current.next;
            }
            temp.next = current.next;
            current.next = null;
        }
        size--;
    }
    

    private boolean isValidIndex(int index){
        return index >= 0 && index <= size;
    }
    
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        
        list.insertFirst(1, "First");

        list.insertLast(2, "Second");

        list.insertLast(3, "Third");
        list.insertAtIndex(4, "Temp", 2);
        System.out.println("After insertion--");
        list.displayList();
        list.removeAtIndex(0);
        System.out.println("After removal--");
        list.displayList();
        System.out.println("Get Node--");
        Node node = list.get(1);
        node.displayData();
    }
}

Output

After insertion--
i= 1 str= First
i= 2 str= Second
i= 4 str= Temp
i= 3 str= Third
After removal--
i= 2 str= Second
i= 4 str= Temp
i= 3 str= Third
Get Node--
i= 4 str= Temp

That's all for this topic Linked List Implementation Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Exponential Search Program in Java
  2. Radix Sort Program in Java
  3. Quick Sort Program in Java
  4. Factorial Program in Java
  5. How to Find First Non-Repeated Character in a Given String - Java Program

You may also like -

>>>Go to Java Programs Page

Tuesday, 12 February 2019

Exponential Search Program in Java

In this post we’ll see how to write Exponential search program in Java. Exponential search is a variation of Binary search, meaning it is also a divide and conquer algorithm how it differs is that rather than dividing the input array into two equal parts in Exponential search a range with in the input array is determined with in which the searched element would reside. Then using Binary search element is searched with in that range.

Exponential search is used to search elements in unbounded arrays.

How does Exponential search work

One of the prerequisite for the Exponential search is that the input array should be sorted.

Exponential search works in two stages. In the first stage a range is calculated that contains the searched element. In the second stage Binary search is done with in that range to search the element.

Exponential search starts by finding the first element that satisfies both of these conditions-

  1. Greater than the searched element
  2. Has index as a power of 2.

This index becomes the upper bound for the range, if such index is j then 2j-1 (or j/2) is the lower bound for the search.

Exponential search Java Program

public class ExponentialSearch {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = {5, 65, 89, 3, 1, 10, 11, 22, 34, 43};
        Arrays.sort(arr);
        System.out.println("Sorted array- " + Arrays.toString(arr));
        System.out.println("Enter value to search: ");
        int searchElement = sc.nextInt();
        int index = exponentialSearch(arr, searchElement);
        if(index != -1){
            System.out.println("Searched item " + arr[index] + " found at index "+index);
        }else{
            System.out.println("Searched item " + searchElement + " not found in the array");
        }
        sc.close();
    }
    
    private static int exponentialSearch(int[] arr, int searchElement){
        int bound = 1;
        // increase upper bound 
        while (bound < arr.length && arr[bound] < searchElement) {
            bound *= 2;
        }
        // do binary search with in the range
        return binarySearch(arr, bound/2, Integer.min(bound + 1, arr.length), searchElement);
    }
    
    private static int binarySearch(int[] arr, int start, int end, int searchElement){
        // exit condition
        if(start > end){
            return -1;
        }        
        int middle = (start+end)/2;
        // element found
        if(searchElement == arr[middle]){
            return middle;
        }
        // left half
        if(searchElement < arr[middle]){
            return binarySearch(arr, start, middle-1, searchElement);
        }else{
                // right half
            return binarySearch(arr, middle+1, end, searchElement);
            
        }
    }
}

Output

sorted array- [1, 3, 5, 10, 11, 22, 34, 43, 65, 89]
Enter value to search: 
10
Searched item 10 found at index 3

Exponential search Performance

The first stage of the algorithm where the range is determined takes O(log i) time, where i is the index of the searched element in the input array.

Second stage where Binary search is done also takes O(log i) for the given range. So the total time taken is 2*O(log i). Thus the time complexity of Exponential search is O(log i).

Space complexity of Exponential search is O(1), for recursive implementation of Binary search method calls are stacked for each recursive call making the space complexity as O(log i) in that case.

That's all for this topic Exponential Search Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Interpolation Search Program in Java
  2. Linear Search (Sequential Search) Java Program
  3. Merge Sort Program in Java
  4. Find Maximum And Minimum Numbers in a Given Matrix - Java Program
  5. Printing Numbers in Sequence Using Threads - Java Program

You may also like -

>>>Go to Java Programs Page

Monday, 11 February 2019

Interpolation Search Program in Java

In this post we’ll see how to write Interpolation search program in Java. Interpolation search is a variation of Binary search, meaning it is also a divide and conquer algorithm how it differs is that rather than dividing the input array into two equal parts it tries to divide the array in such a way that the position is nearer to the searched element.

How does Interpolation search work

One of the prerequisite for the Interpolation search is that the input array should be sorted and the values are uniformly distributed.

Interpolation search takes into account the lowest and highest elements in the array as well as length of the array and tries to estimate the position of the searched element. It works on the principle that the searched element is likely to be located near the end of the array if the searched element is close to the highest element in the array and it is likely to be located near the start of the array if the searched element is close to the lowest element in the array.

Interpolation search uses the following formula to calculate the position to be compared with the searched element.

position = start + ((searchElement - arr[start]) * (end - start) / (arr[end] – arr[start]))

In each iteration searched element is compared with the element at the calculated position and start and end are adjusted based upon whether the searched element is greater than or less than the calculated position.

Interpolation search Java Program

public class InterpolationSearch {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73};
        Arrays.sort(arr);
        System.out.println("sorted array- " + Arrays.toString(arr));
        System.out.println("Enter value to search: ");
        int searchElement = sc.nextInt();
        int index = interpolationSearch(arr, searchElement);
        if(index != -1){
            System.out.println("Searched item " + arr[index] + " found at index "+index);
        }else{
            System.out.println("Searched item " + searchElement + " not found in the array");
        }
        sc.close();
    }
    private static int interpolationSearch(int[] arr, int searchElement){
        int start = 0;
        int end = arr.length - 1;
        int position;
        while ((arr[end] != arr[start]) && (searchElement >= arr[start]) && (searchElement <= arr[end])) {
            position = start + ((searchElement - arr[start]) * (end - start) / (arr[end] - arr[start]));

            // Nearer to the highest element
            if (arr[position] < searchElement)
                start = position + 1;
            // Nearer to the lowest element
            else if (searchElement < arr[position])
                end = position - 1;
            else
                return position;
        }

        if (searchElement == arr[start])
            return start ;
        else
            return -1;
    }
}

Output for few of the searches-

sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73]
Enter value to search: 
55
Searched item 55 found at index 6

sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73]
Enter value to search: 
23
Searched item 23 found at index 4

Interpolation search Performance

Average case time complexity of Interpolation search is O(log(log(n))) if the elements are uniformly distributed. In worst case time complexity can be O(n).

Space complexity of Interpolation search is O(1) as no auxiliary space is required.

That's all for this topic Interpolation Search Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Linear Search (Sequential Search) Java Program
  2. Ternary Search Program in Java
  3. Shell Sort Program in Java
  4. Find Maximum And Minimum Numbers in a Given Matrix - Java Program
  5. Printing Numbers in Sequence Using Threads - Java Program

You may also like -

>>>Go to Java Programs Page