How do I find the smallest item in an array?

Question

I have an array, and need to find the index of the smallest item.

a = [2, 2, 2, 3, 3, 4, 3]

This should return 0.

Please note that the content and ordering of the array must not be modified.

I am looking for a solution in either C or Java.

Answer 1

Erm. In pseudocode:

int low_index = -1;
int low_value;
for(int ix = 0 to length(array)) {
    if(low_index == -1 || array[low_index] < low_value) {
        low_index = ix;
        low_value = array[ix];
    }
}
return low_index;

Answer 2

It should return me the array position of the smallest number.

Simply iterate through the array, keeping track of whether a particular index has a smaller value than the smallest one encountered so far.

In pseudocode:

j = 0

for i = 1 ... arr.length:
  if arr[i] < arr[j]:
    j = i

return j // j now contains the index of the smallest value in the array.

Answer 3

Now i want to find out the smallest no. from the given list of nos. The question is some what tricky in which, we can see a[0] consists of smallest no. but if it is rejected (some logic, due to which it is rejected) then it should call a[1] being the second smallest and third smallest and so on and so forth.. It should return me the array position of the smallest no.

You probably need to keep an additional indices array to index into the original array for the smallest element. And I assume that you want only the smallest and no-fallback on the second smallest or so on?

Answer 4

Check whether the following Java code will satisfy your requirement.

private int min(int[] a, int... reject) {
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < a.length; i++) {
        boolean skip = false;
        for (int r : reject) {
            if (i == r) {
                skip = true;
                break;
            }
        }
        if (!skip) {
            res = Math.min(a[i], res);
        }
    }
    return res;
}

Demo usage.

int[] a = { 2, 2, 2, 3, 3, 4, 3 };
System.out.println(min(a));
// this will print 2
System.out.println(min(a, 0, 1, 2));
// this will print 3

EDIT: You can modify the above function to return the index also.

EDIT2: To Young See Math.min javadoc http://java.sun.com/javase/6/docs/api/java/lang/Math.html#min(int,%20int)

EDIT3:

but can you explain this bit of logic.. as following things are new to me... 1) private int min(int[] a, int... reject) 2) for (int r : reject) { if (i == r) { skip = true; break; } }

1) The signature is making use of variable arguments. So you can pass all the index you want to reject as parameters. 2) The for loop is making sure that if the element with the index is to reject then simply skip it by making the skip flag to true. And we are breaking the loop there itself.

EDIT4: TO ALL - Young changed his question removing the requirement of skipping elements from the array. Now for the current question John Feminella's code snippet is the easiest way.

Answer 5

I think there is a faster way:

void quickSort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

Answer 6

Java:

If you don't worry about performance, which is not an issue for small data sets, you should make use of the collections framework in java.

// Find the smallest number
Integer smallest = new TreeSet<Integer>( Arrays.asList( a ) ).get( 0 );

// Get array index of smallest number
Arrays.asList( a ).indexOf( smallest );

Answer 7

John Feminella is on the right track by iterating once through the array. I think sorting has a few problems: Young says the array can't be changed, and as Pax points out no sort is going to have better performance than iterating over the array once.

If you're interested in why one method is faster than another you might read about Big O Notation. In computer science this is used to describe the growth rate of functions and estimate their running time. Lower-order functions will generally be faster than higher order ones, and this is usually written in terms of the number of elements or n.

For example the iteration that John F. proposed is described as linear and is written as O(n). We only go through the array once and it has n elements. Sorting always requires more operations. Over the years a lot of smart people have come up with sorting algorithms that improve performance, but they all have higher growth rates and are higher order than O(n). For instance Java's Array sort() is O(n*log(n)), and the Wikipedia page for Sorting Algorithms has a table with many more examples.

You may not need it for this project, but I hope it's helpful in the future when you do need to do expensive operations like sorting.

Answer 8

in C

int getMinIndex(int *a, int len)
{
    int i = 0, ret = 0;
    int min = INT_MAX; // defined in <limits.h>

    if (!a || len <= 0)
        return -1;

    for (; i < len; ++ i)
    {
        if (a[i] < min)
        {
            ret = i;
            min = a[i];
        }
    }

    return ret;
}

Answer 9

this can be done in O(n log n) time without reordering the array. Basically, you compare pairs to find the lowest, then compare those pairs to find he lowest out of four, and so on. Easiest way to do it is with recursion.

Start the process get_index_of_lowest(arr, 0, arr.length)

int get_index_of_lowest(int[] arr, int start, int blocksize) {
  if(blocksize == 1) {
     return start;
  }
  else {
    int left = get_index_of_lowest(arr, start, arr.length/2);
    // note that arr.length is potentially odd
    int right = get_index_of_lowest(arr, 
        start + arr.length/2, 
        arr.length - arr.length/2);
    return arr[left] <= arr[right] ? left:right;
  }
}

Without recursion, you need a int[] to use as a stack.

As always with homework questions - please let me know which institution you are at, so I know not to work with anyone from there in future.

Answer 10

Answer in c:

#include<stdio.h>
#include<conio.h>
void main()
{
    int a = [2, 2, 2, 3, 3, 4, 3],i;
    clrscr();
    for (i=0;i<=6;i++)
    {
        for (a[0]>a[i])//if you change > sign into < sign, it will produce first largest no.
        {
            int s;
            s=a[i];
            a[i]=a[0];
            a[0]=a[i];
        }
    }
    printf("Smallest no=%d",a[0]);
    for (i=1;i<=6;i++)
    {
        if (a[1]>a[i])   // if you change >sign to < sign ,it will produce second largest no .
        {
            int t;
            t=a[i];
            a[i]=a[1];
            a[1]=t;
        }
    }
    printf("Second smallest no=%d",a[1]);
    getch();
}

Answer 11

  int main(void) {
  int array[8] = { 60, 25, 734, 6, 40, 2, 0 ,99 };
  int arrayMin[4];
  int arrayMax[4];
  int minValue, maxValue;
  int numOfComparisons = 0;

  /* Partition the mins and maxs */
  int i;
  int s = 0;

  for (i = 1; i < 8; i += 2) {
    numOfComparisons++;
    if (array[i] > array[i-1]) {
      arrayMin[s] = array[i-1];
      arrayMax[s] = array[i];
    }
    else {
      arrayMin[s] = array[i];
      arrayMax[s] = array[i-1];
    }
    s++;
  }
  /* Find min */
  minValue = arrayMin[0];
  for (i = 1; i < 4 ; i++) {
    numOfComparisons++;
    if (arrayMin[i] < minValue) {
     minValue = arrayMin[i];
   }
  }
  printf("Min Value: %d\n", minValue);

  /* Find max */
  maxValue = arrayMax[0];
  for ( i = 1; i < 4; i++) {
    numOfComparisons++;
    if (arrayMax[i] > maxValue) {
      maxValue = arrayMax[i];
    }
  }
  printf("Max Value: %d\n", maxValue);
  printf("Num Of Comparisons: %d\n", numOfComparisons);

   }