sortedIndex for reverse sorted array?

Question

It seems lodash's sortedIndex expects a forward sorted array for its binary search to work. (e.g. [0,1,2,4])

Is there a way to used sortedIndexBy when the array is reverse sorted? (e.g. [4,2,1,0])?

> _.sortedIndex( [0,1,2,4], 3 )
> 3
> _.sortedIndex( [4,2,1,0], 3 )
> 4

To get this to work now, I have to reverse the array, find the sortedIndex, insert the new element, and then un-reverse the array.

Note -- need something which works for sorting strings as well as numbers.

['A','B','D'] into ['D','B','A'] and insert 'C'.

fuyushimoya · Accepted Answer · 2018-10-07 13:06:43Z

5

How about _.sortedIndexBy?

Edited: For string comparison, String.prototype.charCodeAt() can help you convert it to Number, then the same logic can be applied.

const arr1 = [0, 1, 2, 4];
const arr2 = [4, 2 ,1, 0];

console.log(_.sortedIndex(arr1, 3 ));
// Similar, but with ranking function.
console.log(_.sortedIndexBy(arr2, 3, function(x) {return -x;}));

const charArr = ['D','B','A'];
// Take the first char and convert to Number
let index = _.sortedIndexBy(charArr, 'C', function(x) {
  // Type checks. (If you want it to be general to many types..
  if (typeof x === 'string') {
    return -x.charCodeAt(0);
  } else if (typeof x === 'number') {
    return -x;
  } // else ... for other types.....
});

console.log('To insert char C, put it to index: ', index);

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.13.1/lodash.min.js"></script>

or by _.sortedIndex, it also has iteratee to rank before 4.0.0

    const arr1 = [0, 1, 2, 4];
    const arr2 = [4, 2 ,1, 0];

    console.log(_.sortedIndex(arr1, 3));
    console.log("Reversed order without ranking func: ",_.sortedIndex(arr2, 3));
    // Ranking function to inverse the order.
    console.log("Reversed order with ranking func: ",_.sortedIndex(arr2, 3, function(x) {return -x;}));

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/1.3.1/lodash.min.js"></script>

Thanks to pilau: The sortedIndex expects the array is forward sorted, so we can't just put the reverse sorted array and get arr.length - index, and in order to handle vary scenario, I think we need to do either

Reverse array -> get sorted index and put -> reverse it again. or
Get reversed copy by slice and reverse -> get sorted index and calculate by arr.length - index -> inserted to origin array.

To achieve the expected result.

edited Oct 7, 2018 at 13:06

answered Jul 19, 2016 at 2:39

fuyushimoya

9,8133 gold badges30 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

jedierikb Over a year ago

Good idea! Alas, I sometimes need to sort strings this way. ['A','B','D'] into ['D','B','A'] and insert 'C'.

fuyushimoya Over a year ago

Updated for string case.

jedierikb Over a year ago

But for longer strings ('AAA', 'AAB', 'AAC') one would have to iterate through the string to convert each char. I fear it might be faster to reverse at that point.

fuyushimoya Over a year ago

When using the sortedIndex, do you know if the array is reversed sorted or not? If yes, you can just get the value as its normally sorted, then use realIndex = length - index; to get the position in the reversed array :P.

pilau Over a year ago

@fuyushimoya _.sortedIndex([40, 30, 10], 20); yields 0. Array length (3) - 0 equals 3. The resulted array would be [40, 30, 10, 20], meaning realIndex = length - index; would not work - unless I am missing something, of course :)

|

Collectives™ on Stack Overflow

sortedIndex for reverse sorted array?

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related