Approach 1: Binary Search
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.
Initialise left and right pointers :
left = 0,
right = n - 1.
left <= right:
Compare middle element of the array
nums[pivot]to the target value
If the middle element is the target
target = nums[pivot]: return
If the target is not yet found :
target < nums[pivot], continue the search on the left
right = pivot - 1.
Else continue the search on the right
left = pivot + 1.
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.