We use a loop to do binary search on a sorted array.
We start with two markers, one on each end: start and end.
We then calculate mid. We compare the value at index mid to the value we’re trying to insert.
If our to insert value is larger, we move our start to mid + 1.
If our to insert value is smaller, we move our end to mid – 1.
This way, we squeeze our start and end markers tighter and tighter.
Once we squeeze where start <= end is false (AKA start > end )…our mid is at the correct index. All we need to do is see if our to insert value is larger or smaller than the value at index mid.
If larger, arr.splice(mid+1, 0)
If smaller, arr.splice(mid, 0)
Because by default splice at an index will add the value at that index and push everything down.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// given inputs let arr = [8, 14, 53, 65]; let toInsert = 99; // params used to locate let start = 0; let mid = 0; let end = arr.length-1; // Let's squeeze start and end together while (start <= end) { mid = Math.ceil((start+end)/2); // we always get ceiling if (toInsert < arr[mid]) { end = mid-1; // if our # is smaller, squeeze in from top } else { start = mid+1; // if our # is bigger, squeeze in from bottom } } // location found on mid, because we've been squeezed out. // if our number is smaller than value at index mid, we put it in front if (toInsert < arr[mid]) { arr.splice(mid, 0, toInsert); } // if our number is larger than value at index mid, we put it after if (toInsert > arr[mid]) { arr.splice(mid+1,0, toInsert); } |