c - Searching missing number - simple example -

a little task on searching algorithm , complextiy in c. want make sure im right.

i have n natural numbers 1 n+1 ordered small big, , need find missing one. example: 1 2 3 5 6 7 8 9 10 11 - ans: 4

the fastest , simple answer 1 loop , check every number number comes after it. , complexity of o(n) in worst case.

i thought maybe missing , can find using binary search. can think on more efficient algorithm in simple example? o(log(n)) or ?

for comparison-based algorithm, can't beat lg(n) comparisons in worst case. because answer number between 1 , n , takes lg(n) bits of information represent such number. (and comparison gives single bit.)

unless distribution of answers skewed, can't better lg(n) on average.

now don't see how non-comparison-based method exploit fact sequence ordered, , better o(n).