Credence.Rule.NoEnumAtBinarySearch (credence v0.3.1)

Performance rule: Flags Enum.at/2 inside recursive binary search functions.

Elixir lists are linked lists. Enum.at/2 is an O(n) operation. Using it inside a recursive binary search results in O(n log n) complexity, defeating the purpose of the algorithm.

Not auto-fixable

Recursive functions require a manual refactor: create a wrapper function that calls List.to_tuple/1, change the recursive helper's signature to accept the tuple, and update all recursive call sites. This structural change cannot be performed safely by an automated tool.

Bad

def search(list, target, low, high) when low <= high do
  mid = low + div(high - low, 2)
  mid_val = Enum.at(list, mid)  # O(n) on every recursive call
  cond do
    mid_val == target -> mid
    mid_val < target  -> search(list, target, mid + 1, high)
    true              -> search(list, target, low, mid - 1)
  end
end

Good

def search(list, target) do
  tuple = List.to_tuple(list)
  do_search(tuple, target, 0, tuple_size(tuple) - 1)
end

defp do_search(tuple, target, low, high) when low <= high do
  mid = low + div(high - low, 2)
  mid_val = elem(tuple, mid)  # O(1)
  cond do
    mid_val == target -> mid
    mid_val < target  -> do_search(tuple, target, mid + 1, high)
    true              -> do_search(tuple, target, low, mid - 1)
  end
end

See also Credence.Rule.NoEnumAtMidpointAccess which catches the same anti-pattern in non-recursive functions and can auto-fix it.