# Well Orderings and Search

DevFeed: [Well Orderings and Search](<https://devfeed.tech/articles/well-orderings-and-search-40202.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/06/14/well-orderings-and-search/>)

Published: 2011-06-14T11:18:04Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Sorting](<https://devfeed.tech/topics/sorting.md>), [ordering](<https://devfeed.tech/topics/ordering.md>), [implementation](<https://devfeed.tech/topics/implementation.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [axiom-of-choice](<https://devfeed.tech/tags/axiom-of-choice.md>), [binary-search](<https://devfeed.tech/tags/binary-search.md>), [mathematica](<https://devfeed.tech/tags/mathematica.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [ordering](<https://devfeed.tech/tags/ordering.md>), [pseudocode](<https://devfeed.tech/tags/pseudocode.md>), [recursion](<https://devfeed.tech/tags/recursion.md>), [sorting](<https://devfeed.tech/tags/sorting.md>), [well-ordering](<https://devfeed.tech/tags/well-ordering.md>)

## AI overview

This tutorial explains binary search on sorted lists, including its recursive structure and O(log n) runtime. It then introduces strict total and well orders to explain why sorting and comparison work.

## Source excerpt

Binary Search Binary search is perhaps the first and most basic nontrivial algorithm a student learns. For the mathematicians out there, binary search is a fast procedure to determine whether a sorted list contains a particular element. Here is a pseudocode implementation: # Binary Search: # Given a list L, sorted via the total order <, and a sought # element x, return true iff L contains x. function binarySearch(L, x, <): # base case if(length(L) == 1): return L[0] == x middleIndex = floor(length(L) / 2) if (L[middleIndex] == x): return true # inductive step, with ellipsis notation meaning slices of L # from the beginning and to the end, respectively if (x < L[middleIndex]): return binarySort(L[.