{
  "path": "/posts/2015/2015-09-06-elixir-binary-search",
  "site": "at://did:plc:mracrip6qu3vw46nbewg44sm/site.standard.publication/self",
  "tags": [
    "code",
    "elixir"
  ],
  "$type": "site.standard.document",
  "title": "Elixir binary search",
  "updatedAt": "2015-09-06T19:08:00.000Z",
  "publishedAt": "2015-09-06T19:08:00.000Z",
  "textContent": "A few days ago, I saw a Guess my word game on the front page of Hacker News. Before spoiling the fun for myself by checking out the comments, I decided to try my hand at writing a solution in Elixir. Afterwards, I generalized the code to choose its own word from the UNIX dictionary and then \"guess\" it, applying a binary search based on the feedback of whether each guess was alphabetically greater or less than the word itself.\n\nExample output:\n\nSomething I encountered worth mentioning is how Elixir compares strings that have different capitalization. Capital letters are \"less than\" their lower case versions:\n\nKnowing this, we use String.downcase in our implementation to avoid comparison issues in the binary search. Binary search has a time complexity of log₂(N).\n\nGiven that the UNIX dictionary has 235,886 words\n\nthe fact the our algorithm took 14 steps to \"guess\" the word is plausible given\n\nO(log₂(235886)) ≈ O(17.85)\n\nwhich is the number of steps we would expect it to take to guess our word.",
  "canonicalUrl": "https://www.danielcorin.com/posts/2015/2015-09-06-elixir-binary-search"
}