Editing Binary search (section)

=== Linear search ===
[[Linear search]] is a simple search algorithm that checks every record until it finds the target value. Linear search can be done on a linked list, which allows for faster insertion and deletion than an array. Binary search is faster than linear search for sorted arrays except if the array is short, although the array needs to be sorted beforehand.{{Efn|{{Harvnb|Knuth|1998}} performed a formal time performance analysis of both of these search algorithms. On Knuth's [[MIX (abstract machine)|MIX]] computer, which Knuth designed as a representation of an ordinary computer, binary search takes on average <math display="inline">18 \log n - 16</math> units of time for a successful search, while linear search with a [[sentinel node]] at the end of the list takes <math display="inline">1.75n + 8.5 - \frac{n \text{ mod } 2}{4n}</math> units. Linear search has lower initial complexity because it requires minimal computation, but it quickly outgrows binary search in complexity. On the MIX computer, binary search only outperforms linear search with a sentinel if <math display="inline">n > 44</math>.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}{{Sfn|Knuth|1998|loc=Answers to Exercises  (§6.2.1) for "Exercise 5"}}}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table")}} All [[sorting algorithm]]s based on comparing elements, such as [[quicksort]] and [[merge sort]], require at least <math display="inline">O(n \log n)</math> comparisons in the worst case.{{Sfn|Knuth|1998|loc=§5.3.1 ("Minimum-Comparison sorting")}} Unlike linear search, binary search can be used for efficient approximate matching. There are operations such as finding the smallest and largest element that can be done efficiently on a sorted array but not on an unsorted array.{{Sfn|Sedgewick|Wayne|2011|loc=§3.2 ("Ordered symbol tables")}}