Scale Engineer

Binary Search

Easy
#0658Time: O(n) - In the worst-case scenario, we might have to scan the entire array of size 'n' to find the target or determine it's not present.Space: O(1) - We only use a constant amount of extra space for variables like the loop counter.7 companies
Algorithms
Binary Search
Data structures
Array
Companies
AccentureCognizantEPAM SystemsInfosys

Prompt

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:

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

 

Constraints:

  • 1 <= nums.length <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to iterate through each element of the array and check if it matches the target. This method does not take advantage of the sorted nature of the array.

Algorithm

  • Iterate through the array nums from index i = 0 to nums.length - 1.
  • For each element nums[i], compare it with target.
  • If nums[i] == target, return the index i.
  • If the loop finishes, it means the target was not found. Return -1.

Walkthrough

This brute-force method involves a simple loop that traverses the array from the first element to the last. In each iteration, we compare the current element with the target value. If the current element is equal to the target, we have found our element, and we return its index. If the loop completes without finding the target, it means the target is not present in the array, so we return -1.

class Solution {    public int search(int[] nums, int target) {        for (int i = 0; i < nums.length; i++) {            if (nums[i] == target) {                return i;            }        }        return -1;    }}

Complexity

Time

O(n) - In the worst-case scenario, we might have to scan the entire array of size 'n' to find the target or determine it's not present.

Space

O(1) - We only use a constant amount of extra space for variables like the loop counter.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Inefficient for large datasets as it doesn't utilize the sorted property of the array.

  • Fails to meet the O(log n) time complexity requirement of the problem.

Solutions

public class Solution {    public int Search(int[] nums, int target) {        int left = 0, right = nums.Length - 1;        while (left < right) {            int mid = (left + right) >> 1;            if (nums[mid] >= target) {                right = mid;            } else {                left = mid + 1;            }        }        return nums[left] == target ? left : -1;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem