Skip to main content

Javascript insort function

I recently had the need for some sorted insertion in Javascript arrays, thought I'd share this tiny bit of code:


Array.prototype.bisect = function(x, lo, hi) {
var mid;
if(typeof(lo) == 'undefined') lo = 0;
if(typeof(hi) == 'undefined') hi = this.length;
while(lo < hi) {
mid = Math.floor((lo + hi) / 2);
if(x < this[mid]) hi = mid;
else lo = mid + 1;
}
return lo
}

Array.prototype.insort = function(x) {
this.splice(this.bisect(x), 0, x);
}


Of course, these methods only work on an already sorted (or empty) array, so if you're using them on an array that came from elsewhere, sort it first. But once sorted, these insertions will maintain the sortedness, no need to 'push' and 'sort' every time you need to insert something into a sorted array.

(lo and hi parameters are optionally possible for the bisection method to allow restricted searches)

Comments

Popular posts from this blog

Procedural music with PyAudio and NumPy

Combining two of my favorite pastimes, programming and music... This is the hacky "reduced to it's basic components" version of a library I've been working on for generating music and dealing with music theory.

Tweaking the harmonics by changing the shape of the harmonic components and ratios can produce some interesting sounds. This one only uses sine waveforms, but a square / saw generator is trivial with numpy.

It takes a second to generate, so don't turn your volume up too loud in anticipation (it may be loud).

import math
import numpy
import pyaudio
import itertools
from scipy import interpolate
from operator import itemgetter


class Note:

NOTES = ['c','c#','d','d#','e','f','f#','g','g#','a','a#','b']

def __init__(self, note, octave=4):
self.octave = octave
if isinstance(note, int):
self.index = note
self.note = Note.NOTES[note]
elif isinstance(note, st…

Build a Feed Reader in Python (Parts 7-9)

Part 07 Adding Jinja2 templates to a flask web application.

 Part 08 Adding static files so we can serve some CSS to style our app.

Part 09 Adding a background task to continuously update the articles while the application is running.

Write a Feed Reader in Python

I just started a new video tutorial series. This time it'll cover the entire process of writing an RSS feed reader in Python from start to finish using the feedparser module, flask, and SQLAlchemy. Expect to see about 3-4 new videos a week until this thing is finished!
Click to watch