Array
Runtime Complexity
- Lookup (by index) - O(1)
- Lookup (by value) - O(n)
- Insert - O(n)
- Delete - O(n)
In cases when lots of inserts/removals are needed, a Linked List is a better option (unless we add/remove in the middle).
Binary Search
var search = function(nums, target) { let minIndex = 0; let maxIndex = nums.length - 1;
while (minIndex <= maxIndex) { let halfIndex = minIndex + Math.floor((maxIndex - minIndex) / 2);
if (nums[halfIndex] === target) { return halfIndex; } else if (nums[halfIndex] < target) { minIndex = halfIndex + 1; } else { maxIndex = halfIndex - 1; } }
return -1;};