C S 313E Lecture Notes - Lecture 5: Binary Search Algorithm, Selection Sort, Insertion Sort
Document Summary
Go as far as you can and backtrack only where necessary. Not guaranteed to find the best solution. Represent a maze using an m x n 2d list containing 0s and 1s. Exit: any 0 located in row 0, row m, column 0, or column n. Starting position: pair of indices in the m x n list. State: representation of where you currently are in solving the problem. History (path to get to this point) Sequential search: moving from item to item, following the underlying sequential ordering until finding the item or running out of items. Uses ordered nature of the list to eliminate half of the remaining items. O(k) operation where k is the size of the slice. File systems use sort all the time. Starting from the left, compare adjacent elements. If they"re in the wrong order, switch them. Move to the next pair and repeat until getting to the end.
