Wednesday 18 May 2016

Find minimum element in array


By using min heap kind of structure we can find the minimum element efficiently. Following is complete working example.

public class MinUtil {
 int getMin(int[] ele) {
  if (Objects.isNull(ele)) {
   throw new NullPointerException("Array shouldn't be null");
  }

  if (ele.length == 0) {
   throw new IllegalArgumentException("Array shouldn't be empty");
  }

  if (ele.length == 1) {
   return ele[0];
  }

  int length = ele.length;

  for (int i = lastNonTerminalNode(ele); i >= 0; i--) {
   int left = leftIndex(i);
   int right = rightIndex(i);

   int tempIndex = i;

   if (ele[tempIndex] > ele[left]) {
    tempIndex = left;
   }

   if (right < length && ele[tempIndex] > ele[right]) {
    tempIndex = right;
   }

   if (tempIndex == i)
    continue;

   int temp = ele[tempIndex];
   ele[tempIndex] = ele[i];
   ele[i] = temp;
  }

  return ele[0];
 }

 private int leftIndex(int i) {
  return 2 * i + 1;
 }

 private int rightIndex(int i) {
  return 2 * i + 2;
 }

 private int lastNonTerminalNode(int a[]) {
  int len = a.length;
  return (len / 2) - 1;
 }
}


import static org.junit.Assert.assertEquals;
import org.junit.Test;

public class MinUtilTet {
 MinUtil obj = new MinUtil();

 @Test
 public void test1() {
  assertEquals(obj.getMin(new int[] { 0 }), 0);
  assertEquals(obj.getMin(new int[] { 0, 1 }), 0);
  assertEquals(obj.getMin(new int[] { 1, 0 }), 0);
  assertEquals(obj.getMin(new int[] { 0, 1, 2 }), 0);
  assertEquals(obj.getMin(new int[] { 1, 0, 2 }), 0);
  assertEquals(obj.getMin(new int[] { 2, 1, 0 }), 0);
  assertEquals(obj.getMin(new int[] { 5, 4, 3, 2, 1, 0 }), 0);
  assertEquals(obj.getMin(new int[] { 5, 4, 3, 2, 1, 0, -1, -2, -3 }), -3);
 }

 @Test(expected = NullPointerException.class)
 public void test2() {
  obj.getMin(null);
 }

 @Test(expected = IllegalArgumentException.class)
 public void test3() {
  obj.getMin(new int[] {});
 }
}


No comments:

Post a Comment