By Long Luo

# Brute Force

The Brute Force solution is so easy.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

# Binary Search

Step-by-step Binary Search Algorithm:

We basically ignore half of the elements just after one comparison.

1. Compare target with the middle element;
2. If target matches with the middle element, we return the mid index;
3. Else If target is greater than the mid element, then target can only lie in the right half subarray after the mid element. So we recursive for the right half;
4. Else (target is smaller) recursive for the left half.

The Key of Binary Search is Narrow the Search Interval, aka reducing the scale of the problem.

Every round exclusive the interval where the target element must not exist, so the scale of the problem is gradually reduced.

## Analysis

• Time Complexity: $O(nlogn)$.
• Space Complexity: $O(1)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗