CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Searching

1. Linear Search
2. Binary Search

1. Linear Search
   • Basic idea: check each element in turn
   • Use: find an element in an unsorted list
   • Cost: O(n)
   • Iterative Linear Search
     package main import "fmt" func linearSearch(a []int, target int) bool { for _, elem := range a { if elem == target { return true } } return false } func main() { fmt.Println(linearSearch([]int{2,6,5,3,9}, 3)) fmt.Println(linearSearch([]int{9,7,8,6,2}, 12)) }
   • Recursive Linear Search
     package main import "fmt" func linearSearch(a []int, target int) bool { if len(a) == 0 { return false } else if a[0] == target { return true } else { return linearSearch(a[1:], target) } } func main() { fmt.Println(linearSearch([]int{2,6,5,3,9}, 3)) fmt.Println(linearSearch([]int{9,7,8,6,2}, 12)) }
   
   
2. Binary Search
   • Basic idea: in a sorted list, check middle element, eliminate half on each pass
   • Use: find an element in an unsorted list
     • Find an element in a sorted list
     • Number-guessing game (eg: guess a random number between 1 and 1000)
     • Find a root (zero) of a function with bisection (adapted binary seacrh)
   • Cost: O(logN)
   • Iterative Binary Search
     package main import "fmt" func binarySearch(a []int, target int) bool { lo := 0 hi := len(a) - 1 for lo <= hi { mid := (lo + hi) // 2 if a[mid] == target { return true } else if a[mid] < target { lo = mid + 1 } else { hi = mid - 1 } } return false } func main() { fmt.Println(binarySearch([]int{1,2,3,8,9}, 8)) fmt.Println(binarySearch([]int{5,7,8,10}, 9)) }
   • Recursive Binary Search (Beautiful)
     package main import "fmt" func binarySearch(a []int, target int) bool { if len(a) == 0 { return false } mid := len(a) / 2 if a[mid] == target { return true } else if a[mid] < target { return binarySearch(a[mid+1:], target) } else { return binarySearch(a[:mid], target) } } func main() { fmt.Println(binarySearch([]int{1,2,3,8,9}, 8)) fmt.Println(binarySearch([]int{5,7,8,10}, 9)) }