Most Efficient Way to Find Leftmost div?

Question

Using jQuery or straight Javascript, I'm looking for the best way to find the leftmost div (or in general the DOM element with the minimum or maximum position on either axis).

So far I have two solutions:

1. Iterate through the div objects that I want to consider, saving the smallest left position found.
2. Build an array of objects and using javascript's sort() function with a comparison function that looks at the left property, then choosing the 0th element.

I know that solution 1 would be O(N), but I'm not sure what the efficiency of the sort() function is in most browsers, or if there is a completely different approach.

Answer 1

Consider this:

1. you keep track of one element and one position, you access each element once
2. you keep track of all elements and access all positions multiple times because of sorting

What do you think is the fastest? :)

Answer 2

Probably not going to do any better than O(n) and the best you'll do pure sorting is O(nlogn). The fastest way would be to walk the DOM. I would call getElementsByTagName("div") and iterate through keeping track of the left most element.

function findLeftMostDiv() {
    var leftest = { "left": 999999999999, elem: null };
    var divs = document.getElementsByTagName("div");

    for(i=0; i<divs.length; i++) {
        var div = divs[i];
        var curleft = findPos(div);
        if(curleft < leftest.left) {
            leftest.left = curleft;
            leftest.elem = div;      
        } 
    } 
    return leftest.elem;               
}

function findPos(obj) {
    var curleft=0;
    if(obj.offsetParent) {
        do {
            curleft += obj.offsetLeft;
        } while (obj = obj.offsetParrent);
    }
    return curleft;
}

Answer 3

option 1: iterate through it only once

var $smallest = {left: 000000000, item: null};
var $left = 0;
$('selector').each(function(){
    $left = $(this).offset().left;
    if ($left < $smallest.left)
    {
        $smallest.left = $left;
        $smallest.item = this;
    }
});

option 2: iterate through it at least twice

var $array = [];
$('selector').each(function(){
    var $this = $(this);
    $array.push({left: $this.offset().left, item: this});
});
$array.sort(function(a,b){
    if (a.left < b.left) return -1;
    if (a.left > b.left) return 1;
    return 0;
});
// smallest is $array[0]

option 1 is always faster in this case since you only have to sort it while selecting, sorting almost comes for free in that case.

edit: of course, using only the DOM for this is again, way faster.