Binary Search Solution

Denisse Damian
March 27, 2024

Hello and welcome back brave human being,

Before we delve into the problem, I want to thank you for sticking with this and solving the problem day in and day out.

Today we are going to tackle a problem that is recurring in every interview and knowing how to successfully implement a binary search will leave your interviewer 🤯 .

Day 16: 704 Binary Search

Given a sorted array and a target, write a function to search the target. If the target exists, then return its index. Otherwise, return -1.

Let’s first think how we would solve it without Binary Search….

Naive Solution:

Iterate through the sorted array and evaluate at each iteration if the iterator is pointing to the target. Return the iterator if it does. This solution is done in an O(N) time complexity.

Binary Search Solution:

To find the target element in the array using a binary search this is how the pattern looks like.

For a binary search, three key variables need to be declared: start, end, and middle.

start = 0

end = Array.size()-1

middle = start + (end - start) / 2

This formulation helps avoid potential integer overflow issues that might arise with the simpler expression middle = (start + end) / 2.

The start pointer can only move to the right, and the end pointer can only move to the left. At every step of this algorithm, evaluate whether the condition has been met and reevaluate the middle value. If it has not been met, we must evaluate where to go next. Whether we move Start or End will depend on the following conditions.

target < array[middle]. Then: start = middle - 1

target > array[middle]. Then: end = middle + 1

target == array[middle] return middle, you’ve found the answer!

Let’s set an example…

Binary Search Solution

Complete Solution:

Binary Search


        #include <vector>

        using namespace std;

        class Solution {
        public:
            int search(vector<int>& nums, int target) {
                int start = 0;
                int end = nums.size() - 1;

                while (start <= end) {
                    int middle = start + (end - start) / 2;
                    if (nums[middle] == target) {
                        return middle;
                    }
                    else if (nums[middle] < target) {
                        start = middle + 1;
                    }
                    else if (nums[middle] > target) {
                        end = middle - 1;
                    }
                }
                return -1;
            }
        };

What is the time complexity of a binary search?

Need motivation to be consistent?

Add this problem to your log and when the challenge is done send it to me! You’ll be in for a treat.

Reply

or to participate.