Worst case complexity for above solution is O(n). Bettet solution is to binary search approach which has worst complexity as O(log n). If middle is not as expected, then missing number is in left side of middle number. Apply the same on sub-array on left side