Contains Element? Editorial

Practice Problem Link: Contains Element? | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted array and a number key, return whether the key is present in the array or not.

Naive Approach

The simple solution is to just iterate the array and find if the key is present in the array by comparing each element of the array with the key.

Analysis

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

Implementation

C++

bool containsElement(vector<int> &arr, int key) {
   int n = arr.size();
   for (int i = 0; i < n; i++) {
       if (arr[i] == key) {
           return true;
       }
   }
   return false;
}

Java

class Solution {
   boolean containsElement (int[] arr, int key) {
       int n = arr.length;
       for (int i = 0; i < n; i++) {
           if (arr[i] == key) {
               return true;
           }
       }
       return false;
   }
}

Optimal Approach

Since the array is sorted. Binary search can be used to check if the key is present in the array.

• Initialize three variables, low = 0, high = n - 1 and mid.
• Perform a binary search while (high >= low) and assign mid = (high + low ) /  2;
• If the key is equal to arr[mid], return true.
• If the key is greater than arr[mid] then search for the key in the second half otherwise search for the key in the first half.

Analysis

• Time Complexity: O(log(n))
• Space Complexity: O(1)

Implementation

C++

bool binarySearch(vector<int> arr, int low, int high, int key) {
   if(high >= low) {
       int mid = (high + low) / 2;
       if (arr[mid] == key) {
           return true;
       } else if (arr[mid] < key) {
           return binarySearch (arr, mid + 1, high, key);
       } else {
           return binarySearch (arr, low, mid - 1, key);
       }
   }
   return false;
}
bool containsElement(vector<int> &arr, int key) {
   int n = arr.size();
   return binarySearch (arr, 0, n - 1, key);
}

Java

class Solution {
   boolean binarySearch(int[] arr, int low, int high, int key) {
       if(high >= low) {
           int mid = (high + low) / 2;
           if (arr[mid] == key) {
               return true;
           } else if (arr[mid] < key) {
               return binarySearch (arr, mid + 1, high, key);
           } else {
               return binarySearch (arr, low, mid - 1, key);
           }
       }
       return false;
   }
   boolean containsElement (int[] arr, int key) {
       int n = arr.length;
       return binarySearch(arr, 0, n - 1, key);
   }
}