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.

postorder

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