What is the time complexity of Binary Search?

The optimal solution has a time complexity of O(log n).

What data structures are used to solve Binary Search?

This problem uses Array, Binary Search. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Binary Search?

Insight 1: The array is sorted, making binary search the natural choice for achieving O(log n) complexity. Insight 2: Binary search repeatedly divides the search interval in half. It compares the middle element of the interval with the target and adjusts the interval accordingly.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Binary Search - LeetCode 704 Solution

Q: Which companies ask LeetCode 704. Binary Search in interviews?

This problem is frequently asked at Accenture, Cognizant, EPAM Systems, Infosys, Wipro and 2 more companies.

Binary Search - Complete Solution Guide

Binary Search is LeetCode problem 704, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem asks us to implement a binary search algorithm. Given a sorted array of integers `nums` and an integer `target`, we need to find the index of the `target` in the array. If the `target` exists in the array, return its index; otherwise, return -1. A critical constraint is that the algorithm must have O(log n) runtime complexity, which strongly suggests using binary search.

Solution Approach

The solution uses the standard binary search algorithm. We initialize `left` to 0 and `right` to the last index of the array. Then, while `left` is less than or equal to `right`, we calculate the middle index `mid`. If the element at `nums[mid]` is equal to the `target`, we return `mid`. If `nums[mid]` is less than the `target`, we update `left` to `mid + 1` to search in the right half. If `nums[mid]` is greater than the `target`, we update `right` to `mid - 1` to search in the left half. If the loop finishes without finding the `target`, we return -1.

Step-by-Step Algorithm

Step 1: Initialize `left` to 0 and `right` to `len(nums) - 1`.
Step 2: While `left <= right`, repeat steps 3-6.
Step 3: Calculate `mid = left + (right - left) // 2`. This prevents potential integer overflow.
Step 4: If `nums[mid] == target`, return `mid`.
Step 5: If `nums[mid] < target`, set `left = mid + 1`.
Step 6: If `nums[mid] > target`, set `right = mid - 1`.
Step 7: If the loop finishes without finding the target, return -1.

Key Insights

Insight 1: The array is sorted, making binary search the natural choice for achieving O(log n) complexity.
Insight 2: Binary search repeatedly divides the search interval in half. It compares the middle element of the interval with the target and adjusts the interval accordingly.
Insight 3: Handling the edge cases of the target not being present in the array and ensuring proper loop termination is crucial for a correct solution.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(1)

Topics

This problem involves: Array, Binary Search.

Companies

Asked at: Accenture, Cognizant, EPAM Systems, Infosys, Wipro, Zoho, tcs.

Binary Search | LeetCode 704

Easy

Array Binary Search

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

Solution Code

Available in:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 704: Binary Search - Detailed explanation and solution approaches.

Topics

Array Binary Search

Companies

AccentureCognizantEPAM SystemsInfosysWiproZohotcs

Stats

Difficulty:Easy

Languages:4

Companies:7

Problem #:704

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize `left` to 0 and `right` to `len(nums) - 1`.
2
Step 2: While `left <= right`, repeat steps 3-6.
3
Step 3: Calculate `mid = left + (right - left) // 2`. This prevents potential integer overflow.
4
Step 4: If `nums[mid] == target`, return `mid`.
5
Step 5: If `nums[mid] < target`, set `left = mid + 1`.
6
Step 6: If `nums[mid] > target`, set `right = mid - 1`.
7
Step 7: If the loop finishes without finding the target, return -1.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log n)

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The binary search algorithm divides the search space in half with each comparison, leading to a logarithmic time complexity. The space complexity is constant because the algorithm only uses a fixed number of variables, independent of the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Linear Search

Iterate through the array and compare each element with the target. If a match is found, return the index. Otherwise, return -1.

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

Trade-offs: Linear search is simpler to implement, but it's much less efficient for large arrays because of the O(n) time complexity. It should only be used if binary search is not possible (e.g., the array is not sorted) or for very small arrays where the difference in performance is negligible.

✨

Key Insights

1Insight 1: The array is sorted, making binary search the natural choice for achieving O(log n) complexity.
2Insight 2: Binary search repeatedly divides the search interval in half. It compares the middle element of the interval with the target and adjusts the interval accordingly.
3Insight 3: Handling the edge cases of the target not being present in the array and ensuring proper loop termination is crucial for a correct solution.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: `target` is not present in `nums`. The while loop terminates when `left > right`, and the function returns -1.
Edge case 2: `nums` is empty. The `right` variable is initialized to `-1`, and the `while` loop is never entered, so -1 is returned, which is correct.
Edge case 3: `target` is the first or last element of `nums`. Binary search will find it correctly during its iterations.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly calculating the middle index, potentially leading to integer overflow. Using `mid = left + (right - left) // 2` instead of `mid = (left + right) // 2` avoids this issue. Although integer overflow is usually not an issue with most test cases on LeetCode, it's a good habit to use the safer calculation.

✗Common mistake 2: Using the wrong comparison operator in the `while` loop condition. Using `left < right` instead of `left <= right` can lead to incorrect results, especially when the target is at the end of the array.

✗Common mistake 3: Forgetting to update `left` or `right` correctly after comparing `nums[mid]` with the `target`. It's important to update them to `mid + 1` or `mid - 1` to exclude `mid` from the next search interval.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Searching for a specific entry in a sorted phone book or dictionary. Binary search significantly speeds up the lookup process.

🏦Real-world scenario 2: Finding a specific version of a file or software in a sorted list of versions. This is common in version control systems.

🎮Real-world scenario 3: Implementing efficient search functionality in databases. Databases often use indexed data structures that leverage binary search principles for fast data retrieval.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 12, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I avoid off-by-one errors in binary search?

Use the pattern: left = 0, right = n-1, while (left <= right), mid = left + (right - left) / 2. Decide if you need to find exact match, first occurrence, or last occurrence, and adjust your conditions accordingly. Test with arrays of size 0, 1, and 2.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Binary Search"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?