Binary Search Explained | LeetCode Solution

Binary Search is a divide and conquer algorithm that finds a particular element within a sorted array or a given integer range. Binary search checks the middle element of the array and if it is the required target, it returns true, otherwise it eliminates the one half of the array (half in which the target element cannot lie) and checks the other half. And it repeats this procedure, until it founds the target element or entire array is exhausted (in which case it returns false).

Pseudocode (Recursive Approach)

Binary-Search (arr, low, high, target)
if low > high:
  return false
mid = (low+high)/2
if target == arr[mid]:
  return true
if target < arr[mid]:
  return Binary-Search (arr, low, mid-1, target)
else:
  return Binary-Search (arr, mid+1, high, target)

Pseudocode (Iterative Approach)

Binary-Search (arr, low, high, target)
while low <= high:
  mid = (low+high)/2
  if target == arr[mid]:
    return true
  if target < arr[mid]:
    high = mid-1
  else:
    low = mid+1

Time Complexity of Binary Search: O(logn)
(Since in each step we are halving the search to the 1/2th of the remaining array). You could read the complete time complexity analysis here.

Problem

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.

LeetCode Problem Link

Sample Input

nums = [-1,0,3,5,9,12], target = 9

Sample Output

4

Explanation: 9 exists in nums and its index is 4

Code Implementation

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        
        while (l <= r) {
            int mid = l + (r-l)/2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid+1;
            } else {
                r = mid-1;
            }
        }

        return -1;
    }
};

Time complexity: O(logn), where n is the length of nums vector

Note:
Since Binary Search is an O(logn) algorithm, it could also be used when we need to find a particular target value (mostly an integer), like a prime number in a large range (range > 10⁸).