Binary Search Based Problems

Local Minima 

1). For example in the array 9,6,2,14,5,7,4 – 2 is a local minima as it is smaller than its left and right number 6 and 14. Similarly 5 is another local minima as it is between 14 and 7, both larger than 5. You need to find any one of the local minima.

/* package whatever; // don't place packageg name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
                int arr[] = {1,5,17,15,12,10,7,11,6,2,4};
int min = localMin(arr , 0 , arr.length  -1);
System.out.println("Min " + min);

}

public static int localMin(int[] arr , int start , int end) {
if (arr.length == 1) {
return arr[0];
}
if (arr.length == 2) {
if (arr[0] < arr[1]) {
return arr[0];
} else {
return arr[1];
}
}
int mid = (start + end) / 2;
if (arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1]) {
return arr[mid];
} if (arr[mid-1] < arr[mid]) {
return localMin(arr ,start , mid-1);
} else {
return localMin(arr,mid+1,end);
}
}
}

Missing Number in An Array

2). You are given an array of n – 1 unique numbers in the range from 0 to n – 1. There is only one number missing in the range from 0 to n – 1 . 

Since numbers from 0 to n – 1 are sorted in an array, the first numbers should be same as their indexes. That’s to say, the number 0 is located at the cell with index 0, the number 1 is located at the cell with index 1, and so on. Therefore, it is required to search in an array to find the first cell whose value is not identical to its value. Since the array is sorted, we could find it in O(log n) time based on the binary search algorithm as implemented below:

/* package whatever; // don't place packageg name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {0, 1,2,4,5,6,7 , 8,9,10,11,12,13,14,15,16,17,18};
int number = missingNumber(arr , 0 , arr.length -1);
System.out.println("Missing " + number);

}

public static int missingNumber(int[] a , int start , int end) {
int mid = (start + end) /2;
if (a[mid] != mid && a[mid-1] == (mid -1)) {
return mid ;
}
if (a[mid-1] == (mid -1)) {
return missingNumber(a, mid+1 , end);
} else {
return missingNumber(a ,start , mid-1);
}
}
}

Find the Minimum Element in the Rotated Sorted array

3). Find the minimum element in the rotated sorted array.

For example we have array as  1,3,6,9,12,15.

Now suppose the array is rotated k times ( we don’t know k), such that array becomes

12,15,1,3,6,9

/* package whatever; // don't place packageg name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

int arr[] = {6,9,12,15,1,3};

int elem = minElement(arr , 0 , arr.length-1);

System.out.println("Minimum " + elem);

}

public static int minElement(int[] a , int start , int end) {

int mid = (start + end) /2 ;

if (start == mid) {

return a[mid + 1];

}

if (a[start] > a[mid]) {

return minElement(a,start,mid-1);

}

else {

return minElement(a,mid+1,end);

}

}

}

Find a Peak Element in Array

4). A peak element in an integer array is defined as an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [2, 4, 8, 3], 8 is a peak element and your function should return the index number 2.

/* package whatever; // don't place packageg name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

        int arr[] = {1,5,9,11,13,2,6,3,14};

int peak = peakElement(arr , 0 , arr.length  -1);

System.out.println("Peak " + peak);

}

public static int peakElement(int[] arr , int start , int end) {

if (arr.length == 1) {

return arr[0];

}

if (arr.length == 2) {

if (arr[0] > arr[1]) {

return arr[0];

} else {

return arr[1];

}

}

int mid = (start + end) / 2;

if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]) {

return arr[mid];

} if (arr[mid-1] > arr[mid]) {

return peakElement(arr ,start , mid-1);

} else {

return peakElement(arr,mid+1,end);

}

}

}

Java Initialization blocks, constructors and order of execution

Hi folks ,

This session brings to you the understanding of what initialization blocks are and how they are executed in java programs.

Initialization blocks are the blocks of code where one can perform operations like initialization of variables or execution of some statements. They are of two types :

1. static initialization blocks
2. instance initialization blocks.

Static initialization blocks are static and hence they belong to a particular class and not to the instances of class. e.g.

static {
         // piece of code
}

Instance initialization blocks do not belong to a class and they are executed every time a new instance of the class is created. e.g.

{
        // piece of code
}

Let's write a basic simplest java program with a base Class and another subclass extending this base Class , write parameterized constructors , empty constructors , with static and instance initialization blocks both in base class and sub class .

BaseClass : 

package execOrder;

public class BaseClass {

    private String baseClassStr;
    private boolean baseClassBool;
   
    static {
        System.out.println("BaseClass static init block 1");
    }
   
    {
        System.out.println("BaseClass instance init block 1");
    }
   
    public BaseClass(boolean baseClassBool) {
        this.baseClassBool = baseClassBool;
        System.out.println("BaseClass constructor - baseClassBool is : " + baseClassBool);
    }
   
    public BaseClass() {
        System.out.println("BaseClass no Args Constructor");
    }

    static {
        System.out.println("BaseClass static init block 2");
    }
   
    {
        System.out.println("BaseClass instance init block 2");
        System.out.println("baseClassBool is : " + baseClassBool);
    }  
}

SubClass :

package execOrder;

public class SubClass extends BaseClass {

    private String subClassStr;
    private int subClasssInt;

    static {
        System.out.println("SubClass static init block 1");
    }

    public SubClass(String val) {
        super(true);
        System.out.println("SubClassConstructor : subClassInt =  " +  subClasssInt);
        this.subClassStr = val;
        System.out.println("SubClassConstructor : subClassStr =  " +  subClassStr);
    }

    public SubClass() {
        super();
        System.out.println("SubClass no Args Constructor");
    }

    {
        System.out.println("SubClass instance init block 1");
    }

    static {
        System.out.println("SubClass static init block 2");
    }

    {
        System.out.println("SubClass instance init block 2");
        System.out.println("SubClassInt =  " +  subClasssInt + " SubClassStr = " + subClassStr);
        subClasssInt = 1;
        System.out.println("SubClassInt =  " +  subClasssInt);
    }
   
    public static void main(String[] args) {
        new SubClass();
 System.out.println("--------------################--------------");
        new SubClass("start");
    }
} 

-----------------------------------------------------------------
Console Output : 
BaseClass static init block 1
BaseClass static init block 2
SubClass static init block 1
SubClass static init block 2
BaseClass instance init block 1
BaseClass instance init block 2
baseClassBool is : false
BaseClass no Args Constructor
SubClass instance init block 1
SubClass instance init block 2
SubClassInt =  0 SubClassStr = null
SubClassInt =  1
SubClass no Args Constructor
--------------################--------------
BaseClass instance init block 1
BaseClass instance init block 2
baseClassBool is : false
BaseClass constructor - baseClassBool is : true
SubClass instance init block 1
SubClass instance init block 2
SubClassInt =  0 SubClassStr = null
SubClassInt =  1
SubClassConstructor : subClassInt =  1
SubClassConstructor : subClassStr =  start

Let's try to analyse the above output : 

new SubClass(); calls the subClass constructor , and at this point of time all the static initialization happens in order of derivation of classes , here Base class first and Sub class later.This happens only once when the class is loaded into the JVM . These set of statements will not be executed for further object creation of this class.
 
--------------
BaseClass static init block 1
BaseClass static init block 2
SubClass static init block 1
SubClass static init block 2
--------------
 
The static initialization blocks got executed in order of inheritance.


Next is what , next though the control was passed to the constructor of the subclass which called super() passing control to the constructor of the base class . Now before the constructor actually executes code , some important activities are done .

-> Instance variables are initialized to default values. In this case baseClassStr will get a value null and baseClassBool will get the default value false.
-> Then the instance initialization blocks are executed in order of their appearance in the code.

------------------
BaseClass instance init block 1
BaseClass instance init block 2
baseClassBool is : false // value is by default initialization.
------------------ 

Then finally the constructor's code of the super class got executed and prints: 
------------------
BaseClass no Args Constructor
------------------

Similarly now control comes back to sub class and the same set of activities happen in the sub class as well.

------------------ // instance init blocks
SubClass instance init block 1
SubClass instance init block 2
------------------
SubClassInt =  0 SubClassStr = null // default initialization
------------------
SubClassInt =  1 // explicit initialization as part of instance
                 // init block 
------------------
SubClass no Args Constructor  // and finally the sub class
                              // constructor.
------------------ 

The next of line in code creates another object of the sub class but this time calling the parametrized constructor.

The same set of activities happen in the base class first and then in the sub class , except for the static blocks getting called and executed again , because they are called only once during class loading and are not called per instance creation of the class unlike Instance initialization block which is called for each instance created of the class.

Base class execution 
-----------------
BaseClass instance init block 1
BaseClass instance init block 2
baseClassBool is : false
BaseClass constructor - baseClassBool is : true
-----------------

Sub class execution
-----------------
SubClass instance init block 1
SubClass instance init block 2
SubClassInt =  0 SubClassStr = null
SubClassInt =  1
SubClassConstructor : subClassInt =  1
SubClassConstructor : subClassStr =  start
-----------------

To summarize : 

1. Static initialization happens when class is loaded into the JVM .This piece of code is only executed once.
2. Next , the constructor is called and calls the super class constructors till the top most class Object.class's constructor gets called.
3. In the top most base class , the instance variables get their default values. 
4. The initialization blocks get executed in the order of appearance in the code. Instance initialization code is run for each instance of the class created.
5. The part of the code written in constructor of the super-most class , now gets executed. 
6. The same set of steps if followed until the all the above operations are considered done in the lower most sub Class.

Hope this session taught you something new and now you understand the concepts being discussed here .

Happy Learning .