I'm trying to adapt this `c++`

implementation of the famous kth element of two sorted array algorithm to my application (where the second array is sorted in *increasing* order). Now, I can see two solutions:

- replace the iterator to the elements of
`B`

(the second array) by a reverse_iterator, - try to do it manually, e.g. replace the increments to the pointers of
`B`

by decrements.

Now, I started by trying 2) not so much out of liking but because I'm not so good with using reverse_iterator. However, the "solution" I have doesn't work. I was wondering how one should change the code of J.F. Sebastian to use a reverse iterator for the second array?

```
#include <cmath>
#include <ctime>
#include <functional>
#include <fstream>
#include <iostream>
#include <iterator>
#include <limits>
#include <vector>
#include <random>
#include <inttypes.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <numeric>
#define SIZE(a) (sizeof(a)/sizeof(*a))
#define NDEBUG
using namespace std;
template<class RandomAccessIterator, class Compare>
typename std::iterator_traits<RandomAccessIterator>::value_type
nsmallest_iter(RandomAccessIterator firsta,RandomAccessIterator lasta,RandomAccessIterator firstb,RandomAccessIterator lastb,size_t n,Compare less){//http://stackoverflow.com/questions/4607945/how-to-find-the-kth-smallest-element-in-the-union-of-two-sorted-arrays/11698659#11698659
assert(std::is_sorted(firsta,lasta,less) && std::is_sorted(firstb,lastb,less));
const float x_0=*firsta,x_1=*lastb;
std::cout << x_0 << std::endl;
std::cout << x_1 << std::endl;
for(;;){
assert(n<static_cast<size_t>((lasta-firsta)+(lastb-firstb)));
if(firsta==lasta) return *(firstb+n);
if(firstb==lastb) return *(firsta+n);
size_t mida=(lasta-firsta)/2;
size_t midb=(lastb-firstb)/2;
if((mida+midb)<n){
if(less(*(firstb+midb),*(firsta+mida))){
firstb+=(midb+1);
n-=(midb+1);
} else {
firsta+=(mida+1);
n-=(mida+1);
}
} else {
if(less(*(firstb+midb),*(firsta+mida))){
lasta=(firsta+mida);
} else {
lastb=(firstb+midb);
}
}
}
}
```

Relevant part of the main:

```
const int n=*nr,m=*mr,k=*kr-1;
int i;
float x[n];
srand (time(NULL));
for(i=0;i<n;i++) x[i]=rand();
std::sort(x,x+m,std::greater<float>());
std::sort(x+m,x+n);
*vr=nsmallest_iter(x,x+m,x+m+1,x+n-1,n-2-k,std::greater<float>());
```

With reverse iterators, you need only some little adjustments to the code shown in the link you provided:

```
template<class RandomAccessIterator1, typename RandomAccessIterator2, class Compare>
typename std::iterator_traits<RandomAccessIterator1>::value_type
nsmallest_iter(RandomAccessIterator1 firsta, RandomAccessIterator1 lasta,
RandomAccessIterator2 firstb, RandomAccessIterator2 lastb,
size_t n,
Compare less) {
...
}
```

and

```
int v = nsmallest_iter(
a, a + SIZE(a),
std::reverse_iterator<int*>(b + SIZE(b)), std::reverse_iterator<int*>(b),
SIZE(a)+SIZE(b)-1-i,
std::greater<int>());
```

Similar Questions

I have two dimension array that each 1 layer of elements has different size of array. For example, its something like first element 1 9 second element 7 third element 10 3 2 fourth element 6 92 14 7

I'm trying to find the max and min values of an array. I have 'numArray', which is a string of comma separated numbers (e.g. - 3,5,1,6). I'm using a tokenizer to break them into individual ints and st

I have an array of objects stored in an observableArray, Each array item is a hash of moment.js dates. {startDate:momentObject, endDate:momentObject, cycle:null} I need to compute two things. One will

I have a code for nth largest element in a sorted matrix (sorted row and column wise increasing order) I had some problem doing the (findNextElement) part in the code i.e if the row is exhausted, then

Is this always the case , i mean , that array name is always a pointer to the first element of the array.why is it so?is it something implementation kinda thing or a language feature?

Assume we have an array of length N where the subarrays from 0 to N/2 and N/2 to N elements are sorted. Is it possible to sort the whole array using constant memory in O(N) time? Example of an array:

how to find a random element in a sorted array of unknown length.

Given two sorted arrays of numbers, we want to find the pair with the kth largest possible sum. (A pair is one element from the first array and one element from the second array). For example, with ar

In this post Why is processing a sorted array faster than random array, it says that branch predicton is the reason of the performance boost in sorted arrays. But I just tried the example using Python

I'm learning about binary search and the basic definition starts with an iterator to the first element and another one to the last. You also have a key, which is the element you are looking for. The k

I'm refactoring a project that involves passing around a lot of arrays. Currently, each method that returns an array sorts it right before returning it. This isn't ideal for a couple reasons -- there'

I need to find the intersection of two sorted integer arrays and do it very fast. Right now, I am using the following code: int i = 0, j = 0; while (i < arr1.Count && j < arr2.Count) {

I'm trying to write an algorithm that will return True/False whether a contiguous sequence in a sorted array that contains only positive integers, can sum up to N. For example: Array = { 1, 2, 3, 4 };

I've been implementing selection sort problems for class and one of the assignments is to find the kth smallest element in the array using a minimum heap. I know the procedure is: heapify the array d

I have a sorted array of keys and value like Array ( [1] => Array ( [value] => 65 ...... ) [0] => Array ( [value] => 65 ) [5] => Array ( [value] => 35 ) [4] => Array ( [value] =&

I have written a Fortran90 code to extract angles from molecular simulation data. In this code I used a module with name all_parameter. In this module I defined an array such as: CH_Angles INTEGER

I came across this problem - input - I am given two sorted arrays a1 and a2. I need to find the elements that are not present in the second array. I have two approaches 1) Hashtable - O(m+n) [use whe

i have two sorted dictionaries both with the type signature i.e. SortedDictionary<decimal, long> A SortedDictionary<decimal, long> B I want to merge the two lists where the key is the sam

I try to use randomized pivot method to find the Kth min elem among given array. [The code] public class FindKthMin { // Find the Kth min elem by randomized pivot. private static void exchange (int[

I am wondering if there is an efficient implementation of the quick select algorithm on the GPU. I hope to use the implementation to find the kth largest element. If there is none, I will write my own

My question is with reference to Method 2 of this link. Here two equal length sorted arrays are given and we have to find the median of the two arrays merged. Algorithm: 1) Calculate the medians m1 a

I have two array's containing hashes with product information. The array's are not sorted in a meaningful way. Array A (number of products/hashes = 27.605) contains: itemId description category ex

I am learning how to implement mergesort in c++ and encountered the following problem. This is my merge function that merges two sorted arrays into one sorted array. void merge(int *list, int *final,

I have the the following array of numbers in Ruby (higher is better), and I'd like to rank them. In other words, I want to convert the following sorted list: [89 52 52 36 18 18 5] to the following ra

I am learning ruby and was given the following assignment: given two sorted arrays like the following we must merge them into one sorted array. array_1 = [5,8,9,11] array_2 = [4,6,7,10] merge(array_1,

We have sorted array arr[]={2,4,5,7,8,12,16,18,20}. We need to find out pair of elements whose addition is 12, with complexity O(n). Could anyone help on it?

[Interview Question] Write a function that would return the 5th element from the tail (or end) of a singly linked list of integers, in one pass, and then provide a set of test cases against that funct

I have a hashmap, I wish to get an array of the keys in this hashmap, but I wish for the array to be sorted. For instance if the map looks like this: <2,obj1> <4,obj2> <6,obj3>

Problem: Given an array of integers, find the minimum buffer value such that the array can be sorted in strictly increasing order. Each element in the array can add or subtract up to the buffer value.

Is this possible in PHP? $a = array('first' => 'some value', 'second' => $a['first']); Simply accessing an array element within another element from the same array.

This could sound like a pretty basic question, but I could not find a proper answer to my question. How does Selenium element location implementation work? For example:- When doing findElement by ID,

I know that for arrays you can add an element in a two dimensional array this way: array[0][1] = 17; //just an example How can I do the same thing with ArrayList?

I have an array of sorted ints with a 1,000 or more values (could be up to 5000+). I need to write a function that receives an int and returns a bool based on the element being in the array. I know I

Algorithm for Finding nth smallest/largest element in an array using data strucuture self balancing binary search tree.. Read the post: http://stackoverflow.com/questions/2329171/find-kth-smallest-ele

I am looking for a suitable algorithm to build a relatively small (up to 255 elements) sorted array of integers. The target platform is a STM32 based embedded system. Since memory is limited, an in-pl

Possible Duplicate: How to find the kth smallest element in the union of two sorted arrays? This is a question one of my friends told me he was asked while interviewing, I've been thinking about a s

I'm wondering how to get the next element in a C# sorted list. SO far I've come up with the following code: SortedList<int, Bla> mList; Bla someElement = mList[key]; Bla next = mList[mList.Keys[

I have n arrays. Each of these array can be of infinite length. (length can be variable). All these n arrays are sorted. now i want to fetch out top k largest elements out of these n sorted arrays. Fo

Can anyone give me hint how to develop the suffix array part? I know the concept; LCP array design but I am not getting how to implement it in C? Can anyone please help? I know the uses, algorithm of

I've been playing around with this problem, trying to sort out this multidimensional array but I keep on getting the wrong output. The array is sorted, except for the first element. Everything is in o

I would like to have an observable array which will sort itself when an object is pushed into it (it would be even better if it would sort itself if any of the values it was using in the comparator fu

//EDIT My issue was related to something else, I thought the implementation was incorrect but it actually works, thanks for the confirmation. Looked in jQuery and prototypejs, can't seem to find the w

Have a problem where i am ask to write a program to find the kth order statistic of a data set consisting of character and their occurences. For example i have a data set consiting of B,A,C,A,B,C,A,D;

What would be the quickest way to insert values into the correct position in a numpy sorted array. For example I would like to insert ever value of binto a: a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27

We have an n-node binary heap which contains n distinct items (smallest item at the root). For a k<=n, find a O(klogk) time algorithm to select kth smallest element from the heap. O(klogn) is obvio

I wrote a method to take two sorted arrays and return an array of all of the common values, ignoring duplicates. It has a lot of repetition. I'm not sure if it's just the nature of the question or if

Possible Duplicates: Merging two sorted lists Algorithm for N-way merge Given k sorted arrays each of length n, construct a single merged and sorted array.focus on running time and space complexity.

How do I put values from a sorted list and array into a dictionary and determine how many time numbers repeat themselves? This is my code so far. from numpy import * from random import * lista=[] for

Is there a way to turn a Binary to a sorted array without having to traverse the tree for every array index? Node root; Node runner; int current_smallest; void findsmallest(Node root){ //Pre-order tra

I'm trying to find the fastest way to find the first non-zero value for each row of a two dimensional sorted array. Technically, the only values in the array are zeros and ones, and it is sorted. Fo