Binary Search (704)

LeetCode (C++)

Question

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.Example 1

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Solution

The question states it right away that we are about to use a binary search. You can use a linear search also to solve this exercise but we will consume too much time on solving it and the best possible runtime complexity will be O(n). We will stick to binary search for now and solve this questions as fast as possible.

Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).

Picture by GeeKforgeeks

The idea is to divide the array in 2 and look for the target number in the left side and after that in the right. This method will cut the complixy in 2 for each iteration we will try to find the target number resulting in a complexity of O(logn).

Low in this case is the first element of the vector (vectors in c++ can be used as arrays as well). High in the other hand is the the last element of the vector or the element in the right most of the vector. We calculate the middle of the array (low+hight)/2

For as long as the low is less that high, we check through if statement whether we have found the target number or not. If the target number is the actual middle of the vector we return the middle position. If the target number is bigger than the middle number of the vector, the new low position becomes the middle + 1, and we will focus only on the right part of the vector. If the target is less than the middle of the vector, the high will become middle -1 and we will focus only on the left part of the array. We will constantly find the middle after the first iteration as the low and the high variables change after each iteration. In case that target doesn’t exist in the vector we’ll return -1.

Reference

Binary Search - LeetCode

Join Medium with my referral link - Eniela P. Vela