To Top
# Binary Search Any problem where the solution space is finite (i.e the value will be from [0...n]) and there is a way to quickly determine if a certain solution is correct, then you can approach it using a binary search.
For a normal array with a target search value, your solution is in the array, and you can test if the solution is correct by indexing.
For optimisation type problems, you could approach it by looping over the entire solution space and checking if a solution works, if the solution space is small enough. ```js // Iterative binary search function binarySearch(nums, target) { let lower = 0; let upper = nums.length - 1; // Since setting the bounds using mid will never make // upper > lower, then this condition means when we terminate, // lower == upper. // If instead we had lower <= upper then this may not be true // but if we are returning the index from within the loop then // the <= variant returns simpler code while(lower < upper) { // this adds half the range to lower, to get the mid point const mid = Math.floor((upper - lower)/2) + lower; // Then the condition needed can depend on the question, i.e: // To find the local maximum for example, you'd check // if the last element and next elements are greater than // the current one. // Or for the minimum in a rotated sorted array, you'd find the index // at which the sorted array is pivoted on by checking if the next // element is less than current, or previous is greater than current // (assuming it was sorted in ascending order) if(nums[mid] == target) { return mid; } else if(numd[mid] < target) { // prune off the top portion of the range upper = mid - 1; } else { // otherwise prune off the bottom portion lower = mid + 1; } } } // The recursive approach is basically the same function recurBinSearch(nums, target) { function recurSearch(nums, lower, upper) { const mid = Math.floor((upper - lower)/2) + lower; if(nums[mid] == target) { return mid; } else if(numd[mid] < target) { // prune off the top portion of the range upper = mid - 1; } else { // otherwise prune off the bottom portion lower = mid + 1; } } return recurSearch(nums, 0, nums.length-1); } ``` ## Binary Search, find correct insertion position ```python def searchInsert(nums: List[int], target: int) -> int: left = 0 right = len(nums)-1 while left <= right: mid = (right - left) // 2 + left if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return left # There is an invariant for the program - the target is in the inclusive range [left, right] (A) # Two cases arise by the time the loop exits: # 1. We found the item and returned `mid` # 2. We didn't find the item # In the second case, then we return either `left` or `right`. # In the final iteration, either: # 1. nums[mid] < target, so left_old = mid + 1 # This is final iteration, it exits when `left > right`, so for this case left_old == right_old # So, left_new = mid + 1 -> left_new = left_old + 1 # Since nums[mid] < target here, then insertion at the position left_new is correct # 2. nums[mid] > target, so right_old = mid - 1 # this is final iteration, it exits when `left > right`, so for this case right_old == left_old+1 or right_old == left_old # (right == left+1): then right_new = left_old # (right == left): then right_new = left_old - 1 # The first case wouldn't even arise, since mid = (right_old - left_old) // 2 + left_old, which implies that mid == left_old, # which was already checked in this iteration and would've exited early # The second case violates invariant (A), since that value is in a region which is outside the range in which the # target can exist (either it is outside the bounds of the array, or we've checked that region already), # so the position indicated by `right` wouldn't be the correct position ``` # Bit Operations If an array contains 2 of every number in the array, and you add one more number into it, then you can XOR every element in the new array to find what the number you just added in was, since XORing a number with itself returns 0. # Majority Elements ```js // Used for finding the element that occurs // more than n/2 times in an array of length n function boyerMooreVoting(nums) { // When sum is 0, select this element as next candidate // for majority element if you encounter this element, // increment sum, else decrement. // If you get 0, then this means half the other elements // so far were not this element, so this wasn't a majority // element since the last 0, so you start again. let curr = 0; let sum = 0; for(const n of nums) { if(sum == 0) { curr = n; } if(n == curr) { ++sum; } else { --sum; } } // second pass to make sure it is the majority let occurrences = 0; for(const n of nums) { if(curr == n) { occurrences++; } } return occurrences > nums.length/2 ? curr : -1; } ``` # Sorting ## Quicksort ```js function partition(ns, lower, upper) { // swaps two elements of the array const swap = (i, j) => { const t = ns[i]; ns[i] = ns[j]; ns[j] = t; } // picks the first element as the pivot const pivot = ns[lower]; /* So partitions from [start+1, ..., n, ..., end] then swaps n with start to get the partitioned array. While the item at the start index is <= pivot value we continue, otherwise the item is > pivot, so we swap with the end and decrement the end. This way we build up the array like this: [pivot at start | items <= pivot | not checked items | items > pivot ] ↑ ↑ ↑ ↑ lower lower+1 start end and the final index is upper. As such, we can terminate when end > start, since at that point the item at end will be <= pivot. So we then swap the pivot at the start with the end index, and return the end index as the index of the pivot. */ let start = lower+1; let end = upper; while(start <= end) { if(ns[start] <= pivot) { start++; } else { swap(start, end); end--; } } swap(end, lower) return end; } function quicksort(ns) { function qs(lower, upper) { // no elements in range so return if(lower >= upper) { return; } const pivot = partition(ns, lower, upper); qs(lower, pivot-1) // sort lower half qs(pivot+1, upper) // sort upper half } qs(0, ns.length-1) } ``` # Lambda Calculus (Assuming that numbers are encoded as Church numerals) ```clj ifz = if (m = 0) then x1 else x2 = λm.λx1.λx2.m (λz.x2) x1 mult = λm.λn.λf.λx. m f (n f x) pred = λn.λf.λx.n (λg.λh. h (g f)) (λu.x) (λu.u) ``` The predecessor function first replaces every f in a Church numeral with (λg.λh. h (g f)), basically swapping what it is applied to, then applying the function it was applied to, to f. Then (λu.x) replaces the x in the innermost level of the Church numeral, which gets rid of the innermost f, and replaces it with an x. And then the outer f's all replace h with f, except for the first level. To get rid of the h on the first level, the final lambda (λu.u) is used. Overall then the predecessor function removes the innermost f if it exists, thereby decrementing the Church numeral by one. The function g below is what one step of evaluating a factorial function would be. h is just used as a placeholder function. ```clj g = λf.λn.ifz n 1 (mult n (f (pred n))) h = (λx.x) g (g (g h)) = λf.λn.ifz n 1 (mult n (f (pred n))) (λf.λn.ifz n 1 (mult n (f (pred n))) (λf.λn.ifz n 1 (mult n (f (pred n))) (λx.x))) = λf.λn.ifz n 1 (mult n (f (pred n))) (λf.λn.ifz n 1 (mult n (f (pred n))) (λn.ifz n 1 (mult n ((λx.x) (pred n))))) = λf.λn.ifz n 1 (mult n (f (pred n))) (λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n (mult n ((λx.x) (pred n))))) (pred n')))) = λn''.ifz n'' 1 (mult n'' ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) (pred n''))) g (g (g)) 0 = λn''.ifz n'' 1 (mult n'' ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) (pred n''))) 0 = ifz 0 1 (mult 0 ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) (pred 0))) = 1 g (g (g)) 1 = λn''.ifz n'' 1 (mult n'' ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) (pred n''))) 1 = ifz 1 1 (mult 1 ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) (pred 1))) = mult 1 ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) (pred 1)) = mult 1 ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) 0) = mult 1 ((ifz 0 1 (mult 0 ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred 0))))) = mult 1 1 = 1 g (g (g)) 2 = λn''.ifz n'' 1 (mult n'' ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) (pred n''))) 2 = ifz 2 1 (mult 2 ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) (pred 2))) = mult 2 ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) (pred 2)) = mult 2 ((λn'.ifz n' 1 (mult n' ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred n')))) 1) = mult 2 ((ifz 1 1 (mult 1 ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred 1))))) = mult 2 (mult 1 ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) (pred 1))) = mult 2 (mult 1 ((λn.ifz n 1 (mult n ((λx.x) (pred n)))) 0)) = mult 2 (mult 1 (ifz 0 1 (mult 0 ((λx.x) (pred 0))))) = mult 2 (mult 1 1) = mult 2 1 = 2 ``` The fixed point of a function is a value that is mapped to itself by the function, i.e f(x) = x. Check this link for clarification: https://cs.stackexchange.com/a/3468 And also check lambda calculus slides, slide 93, it shows how fact is a fixpoint of the function F on the page. The Y Combinator is the fixpoint operator, for any f, it beta reduces to f (Y f), f (f (Y f)), f (f (f (Y f))) and so on. ```clj Y = λf.(λx.f (x x))(λx.f (x x)) ``` So factorial can be defined using the function g above as: ```clj fact = Y g = Y (λf.λn.ifz n 1 (mult n (f (pred n)))) ``` Play around with some lambdas on https://lambdacalc.io/ to be more convinced. # Modular Arithmetic ``` (A + B) % C = ((A % C) + (B % C)) % C ``` Which can make some big computations have smaller steps and so be easier to do.