Solution
Approach 1: Binary Search
Intuition
Binary search is a textbook algorithm based on the idea to compare the target value to the middle element of the array.
If the target value is equal to the middle element  we're done.
If the target value is smaller  continue to search on the left.
If the target value is larger  continue to search on the right.
Algorithm

Initialise left and right pointers :
left = 0
,right = n  1
. 
While
left <= right
:
Compare middle element of the array
nums[pivot]
to the target valuetarget
.
If the middle element is the target
target = nums[pivot]
: returnpivot
. 
If the target is not yet found :

If
target < nums[pivot]
, continue the search on the leftright = pivot  1
. 
Else continue the search on the right
left = pivot + 1
.



Implementation
!?!../Documents/704_LIS.json:1000,401!?!
Complexity Analysis

Time complexity : .
Let's compute time complexity with the help of master theorem . The equation represents dividing the problem up into subproblems of size in time. Here at step there is only one subproblem
a = 1
, its size is a half of the initial problemb = 2
, and all this happens in a constant timed = 0
. That means that and hence we're dealing with case 2 that results in = time complexity. 
Space complexity : since it's a constant space solution.