Binary Search - Practice Coding Problems

Binary Search - 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.

Input & Output

Example 1 — Target Found

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

› Output: 4

💡 Note: 9 exists in nums and its index is 4

Example 2 — Target Not Found

$ Input: nums = [-1,0,3,5,9,12], target = 2

› Output: -1

💡 Note: 2 does not exist in nums so return -1

Example 3 — Single Element

$ Input: nums = [5], target = 5

› Output: 0

💡 Note: Target found at index 0 in single-element array

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ < nums[i], target < 10⁴
All the integers in nums are unique
nums is sorted in ascending order

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array and target value

Process

Binary search eliminates half each step

Output

Index of target or -1 if not found

Key Takeaway

🎯 Key Insight: Binary search eliminates half the search space with each comparison by leveraging the sorted array property

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to leverage the sorted array property by using binary search to eliminate half the search space with each comparison. Best approach is binary search with Time: O(log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(1)	Check each element one by one until target is found
Binary Search	O(log n)	O(1)	Divide and conquer by comparing middle element and eliminating half

Linear Search — Algorithm Steps

Iterate through array from index 0
Compare each element with target
Return index if match found, -1 otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at index 0

Compare

Check each element against target

Result

Return index when found or -1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int target) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    printf("%d\n", solution(nums, numsSize, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case, we check every element in the array

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

312.7K Views

Very High Frequency

~15 min Avg. Time

8.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler