Analysis of Algorithms - Find missing Integer in Sorted Array better than O(n) -

i working through analysis of algorithms class first time, , wondering if assist below example. believe have solved o(n) complexity, wondering if there better version not thinking of o(logn)?

let a= a[1] <= ... <= a[n+1] sorted array of n distinct integers, in each integer in range [1...n+1]. is, 1 integer out of {1,...,n+1} missing a. describe efficeint algorithm find missing integer. analyze worst case complexity (number of accesses array a) of algorithm.

the solution have relatively simple, , believe results in worst case n complexity. maybe on thinking example, there better solution?

my solution

for(i = 1; < n +1; i++) :     if(a[i-1] > i) :          return 

the logic behind since sorted, first element must 1, second must 2, , on , forth, until element in array larger element supposed be, indiciating element missed, return element should , have missing one.

is correct logic? there better way go it?

thanks reading , in advance assistance.

this logic correct, not fast enough beat o(n) because check every element.

you can faster observing if a[i]==i, elements @ j < i @ proper places. observation should sufficient construct divide-and-conquer approach runs in o(log₂n):

• check element in middle
• if it's @ wrong spot, go left
• otherwise, go right

more formally, looking spot a[i]==i , a[i+1]==i+2. start interval @ ends of array. each probe @ middle of interval shrinks remaining interval twofold. @ point left interval of 2 elements. element on left last "correct" element, while element on right first element after missing number.