>>109659322 - binary search is the minimum you can expect. The error bound is pretty easy to estimate too. Newton's method isn't much harder, but you can only really ne sure of convergence and error bounds if f'(x) satisfies some conditions on [0,1].
5 - It's a classic combinatorics question, just dressed up in a cute way.
6 - A modified mergesort should work. Sort it once and then use the modified merge sort that checks whatever there's a missimg number when it's on the merge phase.
1, 3, 7 can probably be solved by dynamic programming
