LeetCode 704: Binary Search Solution

Problem Explanation

Explanation

To solve this problem, we can use the binary search algorithm due to its O(log n) time complexity. The idea is to divide the array into two halves at each step and check if the target element lies in the left half, right half, or is equal to the middle element. By iteratively narrowing down the search range, we can efficiently find the target element or determine that it does not exist in the array.

Start with the entire array as the search range.
Calculate the middle index of the current search range.
Compare the middle element with the target:
- If the middle element is equal to the target, return the index.
- If the target is less than the middle element, search in the left half.
- If the target is greater than the middle element, search in the right half.
Repeat the above steps until the search range becomes empty.

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

Solution Code

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return -1;
    }
}

Frequently Asked Questions

How to solve LeetCode 704 (Binary Search)?

This page provides optimized solutions for LeetCode problem 704 (Binary Search) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 704 (Binary Search)?

The time complexity for LeetCode 704 (Binary Search) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 704 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 704 in Java, C++, or Python.

704. Binary Search