javascript: find correct index to place object in sorted array of objects

Question

I have a getSortedIndex function. The function accepts the following arguments:

An array of objects which are sorted by a key.
A new object to be inserted into the array.
The key by which all objects are sorted.

function getSortedIndex(array, objToInsert, key) {
    var low = 0,
    high = array.length,
    value = objToInsert[key];

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (value > array[mid][key]) low = mid + 1;
        else high = mid;
    }
    return low;
}

When the function is called, it returns the index at which the object should be placed into the array:

var sorted_array_of_objects = [
    { 'x': 20 },
    // The new object will be placed here.
    { 'x': 30 },
    { 'x': 30 },
    { 'x': 40 },
    { 'x': 50 }
];
var objectToInsert = { 'x': 30, y: 10 };

getSortedIndex(sorted_array_of_objects, objectToInsert, 'x'); //=> 1

My question

Can you modify the function so it returns the index that would place the new object after the objects in the array that have the same value for the x property? If there are no objects in the array with the same value for the x property, then the normal sort index should be returned.

Here's a demo: http://jsbin.com/sortedIndex/3/edit?javascript,console,output

I think your function is incomplete. You missed some code. Where is mid defined? What's with the ; after while (low >> 1? — Felix Kling
– Felix Kling, Commented Feb 22, 2014 at 23:59

Felix Kling · Accepted Answer · 2014-02-23 00:03:13Z

4

Looks like all you have to do is change the comparison from

if (value > array[mid][key])

to

if (value >= array[mid][key])

so that keeps comparing elements with the same value.

answered Feb 23, 2014 at 0:03

Felix Kling

820k181 gold badges1.1k silver badges1.2k bronze badges

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

2 Comments

Web_Designer Over a year ago

I added a demo to my question, tried your change and it didn't work.

Web_Designer Over a year ago

+1 Take that back, I thought you were telling me to switch out a different operator. You're a genius!

Collectives™ on Stack Overflow

javascript: find correct index to place object in sorted array of objects

My question

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

My question

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related