Java program to check if an array is bitonic

This blog post is about a java program to check whether an array is bitonic or not.

Introduction

A bitonic array for this program is defined as an array of length 'N" and for an index 'K' in this array, where 0<K<N-1, the sequence from 0 to K should be increasing order and from K to N-1 should be in decreasing order.

Eg: {1,5,3}, {1,2,3,10,9,8}

Solution

• From starting position, find the element K, upto which the sequence is in increasing order.
• Check whether the sequence is in decreasing order from K to last element in the array. If not return false.
• Return true after execution of the method.

Program

package techjourney.programs;

/**
 * Created by Sujith Mohan on 7/20/2015.
 * This java program is for checking whether a given array is bitonic or not.
 * A bitonic array for this program is defined as an array of length 'N' and
 * for an index 'K' in this array, where 0<K<N-1, the sequence from 0 to K should be
 * increasing order and from K to N-1 it should be in decreasing order.
 *
 * for eg: [0,2,5,9,8,6] is a bitonic array
 */
public class CheckForBitonicArray {

    public static void main(String args[])
    {
        System.out.println(checkBitonicArray(new int[]{0,1,2,3,10,9,8,7,6})); //bitonic -> true
        System.out.println(checkBitonicArray(new int[]{0,1,2,3,10,9})); //bitonic -> true
        System.out.println(checkBitonicArray(new int[]{5,4,3,2,1})); //bitonic -> false
        System.out.println(checkBitonicArray(new int[]{1,3,5})); //bitonic -> false
    }

    public static Boolean checkBitonicArray(int arr[])
    {
        //minimum length for bitonic array defined in this program is 3
        if(arr.length<3)
        {
            return false;
        }
        int temp1 = arr[0];
        int temp2 = arr[1];

        if(temp1-temp2>0)
        {
            return false;
        }

        for(int i=2;i<arr.length;i++)
        {
            if(arr[i]-temp2<0)
            {
                temp1 = i;
                temp2 = arr[i];
                break;
            }
            else
            {
                temp2 = arr[i];
            }
        }

        for(int i=temp1;i<arr.length;i++)
        {
            if(arr[i]-temp2>0)
            {
                return false;
            }

            else
            {
                temp2 = arr[i];
            }
        }

        return true;
    }
}

In the above program, I have used two for loops to find the position K and to check the elements after K. This is done for better readability of the program. Even using one for loop, the method checkBitonicArray can be implemented.

Good to read

1) Shell script for factorial
2) Sample program using hibernate
3) How to use HSQL database