Finding smallest value in an array most efficiently

Question

There are N values in the array  and one of them is the smallest value  How can I find the smallest value most efficiently

User · Answer

If you want to be really efficient and you have enough time to spent, use SIMD instruction.

You can compare several pairs in one instruction:

r0 := min(a0, b0)
r1 := min(a1, b1)
r2 := min(a2, b2)
r3 := min(a3, b3)
__m64 _mm_min_pu8(__m64 a , __m64 b );

Today every computer supports it. Other already have written min function for you:

http://smartdata.usbid.com/datasheets/usbid/2001/2001-q1/i_minmax.pdf

or use already ready library.

User · Answer

You need too loop through the array  remembering the smallest value you ve seen so far   Like this   int smallest   INT MAX  for  int i   0  i  lt  array length  i          if  array i   lt  smallest            smallest   array i

User · Answer

Richie s answer is close  It depends upon the language  Here is a good solution for java   int smallest    Integer MAX VALUE  int array       Assume it is filled  int array length   array length  for  int i   array length - 1  i  gt   0  i--        if  array i   lt  smallest            smallest   array i             I go through the array in reverse order  because comparing  i  to  array length  in the loop comparison requires a fetch and a comparison  two operations   whereas comparing  i  to  0  is a single JVM bytecode operation  If the work being done in the loop is negligible  then the loop comparison consumes a sizable fraction of the time   Of course  others pointed out that encapsulating the array and controlling inserts will help  If getting the minimum was ALL you needed  keeping the list in sorted order is not necessary  Just keep an instance variable that holds the smallest inserted so far  and compare it to each value as it is added to the array   Of course  this fails if you remove elements  In that case  if you remove the current lowest value  you need to do a scan of the entire array to find the new lowest value

User · Answer

find the min in an array list of  s  array   array 45 545 134 6735 545 23 434     smallest    array 0   for  i 1   i lt count  array    i         if  array  i   lt   smallest           echo  array  i

User · Answer

If they are unsorted  you can t do much but look at each one  which is O N   and when you re done you ll know the minimum     Pseudo-code   small    lt biggest value gt     such as std  numerical limits lt int gt   max for each element in array      if  element  lt  small          small   element   A better way reminded by Ben to me was to just initialize small with the first element   small   element 0  for each element in array  starting from 1  not 0       if  element  lt  small          small   element   The above is wrapped in the algorithm header as std  min element     If you can keep your array sorted as items are added  then finding it will be O 1   since you can keep the smallest at front   That s as good as it gets with arrays

User · Answer

If finding the minimum is a one time thing  just iterate through the list and find the minimum   If finding the minimum is a very common thing and you only need to operate on the minimum  use a Heap data structure   A heap will be faster than doing a sort on the list but the tradeoff is you can only find the minimum

User · Answer

An O 1  sollution might be to just guess  The smallest number in your array will often be 0  0 crops up everywhere  Given that you are only looking at unsigned numbers  But even then  0 is good enough  Also  looking through all elements for the smallest number is a real pain  Why not just use 0  It could actually be the correct result   If the interviewer your teacher doesn t like that answer  try 1  2 or 3  They also end up being in most homework interview-scenario numeric arrays     On a more serious side  How often will you need to perform this operation on the array  Because the sollutions above are all O n   If you want to do that m times to a list you will be adding new elements to all the time  why not pay some time up front and create a heap  Then finding the smallest element can really be done in O 1   without resulting to cheating

User · Answer

The stl contains a bunch of methods that should be used dependent to the problem   std  find std  find if std  count std  find std  binary search std  equal range std  lower bound std  upper bound   Now it contains on your data what algorithm to use  This Artikel contains a perfect table to help choosing the right algorithm     In the special case where min max should be determined and you are using std  vector or      array  std  min element std  max element   can be used

User · Answer

int small a 0   for  int x  a length        if a x  lt small          small a x

User · Answer

If the array is sorted in ascending or descending order then you can find it with complexity O 1   For an array of ascending order the first element is the smallest element  you can get it by arr 0   0 based indexing   If the array is sorted in descending order then the last element is the smallest element you can get it by arr sizeOfArray-1    If the array is not sorted then you have to iterate over the array to get the smallest element In this case time complexity is O n   here n is the size of array   int arr      5 7 9 0 -3 2 3 4 56 -7   int smallest element arr 0    let  first element is the smallest one  for int i  1 i lt sizeOfArray i            if arr i  lt smallest element             smallest element arr i             You can calculate it in input section  when you have to find smallest element from a given array    int smallest element  int arr 100  n  cin gt  gt n  for int i   0 i lt n i      cin gt  gt arr i   if i  0        smallest element arr i     smallest element arr 0     else if arr i  lt smallest element    smallest element   arr i         Also you can get smallest element by built in function   inclue lt algorithm gt  int smallest element    min element arr arr n     here n is the size of array   You can get smallest element of any range by using this function such as   int arr      3 2 1 -1 -2 -3   cout lt  lt  min element arr arr 3     this will print 1 smallest element of first three element cout lt  lt  min element arr 2 arr 5      -2  smallest element between third and fifth element  inclusive     I have used asterisk      before min element   function  Because it returns pointer of smallest element  All codes are in c    You can find the maximum element in opposite way

User · Answer

If you re developing some kind of your own array abstraction  you can get O 1  if you store smallest added value in additional attribute and compare it every time a new item is put into array   It should look something like this   class MyArray   public      MyArray     m minValue INT MAX          void add int newValue                if  newValue  lt  m minValue  m minValue   newValue          list push back  newValue               int min                 return m minValue         private      int m minValue      std  list m list

User · Answer

Procedure   We can use min element array  array size  function   But it iterator that return the address of minimum element   If we use  min element array  array size  then it will return the minimum value of array     C   implementation     include lt bits stdc   h gt    using namespace std     int main            int num       cin gt  gt num       int arr 10         for int i 0  i lt num  i                  cin gt  gt arr i                cout lt  lt  min element arr arr num  lt  lt endl       return 0

User · Answer

smalest number in the array       double small   x 0       for t 0 t lt x t  t                   if x t  lt small                                 small x t                           printf   nThe smallest number is   0 2lf   n  small

[c++] Finding smallest value in an array most efficiently

Examples related to c++

Examples related to arrays