### Finding Second Smallest Element In an Unsorted Array

How should I go about finding the 2nd, or 3rd smallest element in an array?
Where the minimum is not equals to the next minimum.

Here is the psuedocode I've found
 ``1234567891011121314`` ``````void Min(A[i..j], int&min, int &next_min) if (i=j) then min=A[i] and next_min = infinity else mid = (i+j)/2 Min(A[i to mid]),a,b) Min(A[mid+1 to j],c,d) Let min be minimum among a,b,c,d Let next_min be the next_min among a,b,c,d min != next_min``````

Here is what I wrote but it does not seem to work. Can anyone point me to the right direction? Thanks

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091`` ``````#include #include #include using namespace std; void minfind(vector &array,int left,int right, int &min, int &next_min); int main(){ cout << "Enter integers one line at a time. (Enter -999 to terminate)" << endl; vector array; // you can also use an array to do this, e.g., int A[21]; int input; //let user enter till termination condition while(true){ cin >> input; if(input == -999) //check for termination condition break; array.push_back(input); } int imin = 0; int imax = array.size(); int q; int r; minfind(array, imin, imax, q, r); cout<<"Min number is " << r < &array,int left,int right, int &min, int &next_min) { int a; int b; int c; int d; if(left == right){ min = array[left]; next_min = 2147483647; } else { int mid= (right+left)/2; minfind(array,left,mid,a,b); minfind(array,mid+1,right,c,d); if (a

Maybe you're thinking too complicated. Element 2 should be smaller than element 1 yet the highest in its rank. This implies that 3 is smaller than 2, and thus you can use the same loop just with different integers. Check the 4th block of code (containing 2 for loops).

 ``123456789101112131415161718192021222324252627282930`` ``````#include #include int main() { enum {SIZE = 16, NUMS = 100, LIM = 100}; int highest[SIZE] {0}; std::vector v; for (int i = 0; i < NUMS; ++i) v.emplace_back(std::rand() % LIM); for (auto &x : v) if (x > highest[0]) highest[0] = x; for (int i = 0; i < SIZE; ++i) for (auto &x : v) if (x > highest[i + 1] && x < highest[i]) highest[i + 1] = x; for (auto &x : v) std::cout << x << std::endl; for (int i = 0; i < SIZE; ++i) std::cout << i << ": " << highest[i] << std::endl; return 0; }``````
y cant u just use SORT?
with algortihm
@topnik1

Using sort means that equivalent elements come after each other. So vector[0] may contain 99, and so does vector[1] or even vector[2] because you may have the number 99, 3 times in the vector/array.
That is a case that would render nth_element useless too.

If one knows the N-1th smallest value X, then one can write the usual find min element with a twist: call all the <=X values "too big" in the test.

There is always the std::map. Filling it is an implisit sort, and it can hide the repeated values in its value_type.
Last edited on
Topic archived. No new replies allowed.