CMPT 120 Study Guide - Final Guide: Hash Table, Memoization, Linear Search

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 120
• Professor: Steven Pearce

Document Summary

An algorithm to look up a particular value in a list or data structure, usually to find the value and determine position. Also known as sequential search, is a method for finding specific value in list where it checks every one of the list"s elements, one at a time, until specific value is found. In worse case time complexity = n (length of list) Also known as half-interval search, is an algorithm that finds the specific value within an ordered (ascending / descending) array sorted by key value by halving the list until value is found, example of divide&conquer. Example pseudocode: def binarysearch(x: value you want to find, list: list of values) return location #value of location where x is or where x isn"t found. Binary, because it can keep halving the list into smaller components to look for value, whereas, linear needs to go through, at worst, all the values in the list.