In this chapter
- Binary search
- Big O notation run time of algorithm
Binary search algorithm used to find postion of target value a sorted array
repeatedly dividing the search interval in half.
NOTE: Binary search only works on sorted array
example
array = [1,3,5,7,9]
find = 3
Iteration 1 divide into half
arr = [1,3,5,7,9]
index = {0,1,2,3,4}
2 is middle index (low + high ) / 2
high is length of array
Iteration 2 divide again into half => [1,3]
0 is middle index
Iteration 3 => [3]
1 is index where number found
code
function binarySearch(array, item) {
let low = 0
let high = array.length-1
while(low <= high ) {
mid = Math.floor((low + high) / 2);
let num = array[mid]
if(num == item) return mid
else if( num > item) {
high = mid -1
} else {
low = mid + 1
}
}
return -1
}
let myList = [1, 3, 5, 7, 9]
console.log("", binarySearch(myList, 3)); // 1Big O notation tells that how fast is algorithm is. n is number of operations
Algorithm running times grow at different rates
e.g
| Simple search | Binary search | |
|---|---|---|
| 10 element | 10 ms | 7 ms |
| 10,000 element | 100 ms | 14 ms |
| 10,000,000,000 element | 11 days. | 32 ms |
Big O establishes a worst-case run time
in case of simple search O(n) means in worst case you can look through every single entry. may you found it on the first try or at last
-
O(log n), also known as log time. Example: Binary search.
-
O(n), also known as linear time. Example: Simple search.
-
O(n * log n). Example: A fast sorting algorithm, like quicksort
-
O(n2). Example: A slow sorting algorithm, like selection sort
-
O(n!). Example: A really slow algorithm, like the traveling salesperson
- Algorithm speed isn’t measured in seconds, but in growth of the number of operations
- How quickly the run time of an algorithm increases as the size of the input increases.
In this chapter
- arrays and linked lists
- first sorting algorithm
used to store information
- Your computer looks like a giant set of drawers, and each drawer has an address.
- Each time you want to store an item in memory, you ask the computer for some space, and it gives you an address where you can store your item
- If you want store multiple : arrays and lists.
- There isn’t one right way to store items for every use case, so it’s important to know the differences.
used to store a list of elements in memory
The term array refers to all things being stored contiguously (directly next to each other) in memory. If you want to add additional items and you're out of space, you must move them to a different spot in memory every time, which can be a huge nuisance.
workaround is may You can ask computer for 10 slots.
- If you don't need the extra slot, memory is wasted.
- If you add more items to the list, you'll need to relocate them anyway.
With linked lists, your items can be anywhere in memory
It’s like a treasure hunt. You go to the first address, and it says, “The next item can be found at address 123.” So you go to address 123,
e.g
Data | Next] -> [Data | Next] -> [Data | Next] -> [Data | Next] -> NULL
Adding an item to a linked list is easy: you stick it anywhere in memory and store the address with the previous item
Arrays vs Linked lists Array if you want to read random element you can read instanlty with Linked list you have to go fist elment ans then second then third
The elements in an array are numbered. This numbering starts from 0
data | 10 | 20 | 30 | 40 |
index | 0 | 1 | 2 | 3 |
Starting at 0 makes all kinds of array-based code easier to write, so programmers have stuck with it.
The position of an element is called its index.
common operations on arrays and lists.
Array List
Reading O(1) O(n)
Insert O(n) O(1)
Delete O(n) O(1)
Array push (add item at end) and pop (remove item from end) Big O varies its O(1)
arrays see a lot of use because they allow random access. There are two different types of access: random access and sequential access.
Sequential access means reading the elements one by one, starting at the first element. Linked lists can only do sequential access.
A lot of use cases require random access, so arrays are used a lot. Arrays and lists are used to implement other data structures
- its comparison based sorting algorithm
- its sort array by selecting smallest or largest from unsorted array and swapping with a first unsorted element. process goes still array are sorted.
Find the smallest element, swap it with the first, then repeat for the next smallest in the remaining elements. Continue until all elements are in place.
e.g 1
function findSmallest(arr, i, n) {
let smallestIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[smallestIndex]) {
smallestIndex = j;
}
}
return smallestIndex;
}
function selectionSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
let smallest = findSmallest(arr, i, n);
let temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
}
return arr;
}
console.log(selectionSort([5, 3, 6, 2, 10])); // [ 2, 3, 5, 6, 10 ]
// e.g 2
function selectionSort(array) {
for (let i = 0; i < array.length - 1; i++) {
let midIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[midIndex]) {
midIndex = j;
}
}
let temp = array[i];
array[i] = array[midIndex];
array[midIndex] = temp;
}
return array;
}
console.log(selectionSort([5, 3, 6, 2, 11, 10]));