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