## Solution

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 value target.

• If the middle element is the target target = nums[pivot] : return pivot.

• If the target is not yet found :

• If target < nums[pivot], continue the search on the left right = 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 problem b = 2, and all this happens in a constant time d = 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.

Analysis written by @liaison and @andvary