Check perfect square using binary search
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Perfect Square Check (Binary Search)
Given a positive integer `n`, determine whether it is a **perfect square** (i.e., there exists an integer `x` such that `x*x = n`).
### Requirements
- Do **not** use built-in square-root functions.
- Implement an `O(log n)` approach.
### Input
- Integer `n` (`1 <= n <= 2^31 - 1`).
### Output
- Return `true` if `n` is a perfect square, otherwise `false`.
### Examples
- `n = 16` -> `true` (4×4)
- `n = 14` -> `false`
### Notes
- Be careful about integer overflow when computing `mid * mid`.
Quick Answer: This question evaluates a candidate's competency in implementing binary search and handling integer arithmetic and overflow considerations when checking numeric properties. Commonly asked to assess algorithmic complexity analysis and practical coding ability within the Coding & Algorithms domain, it emphasizes practical application and O(log n) performance rather than purely conceptual reasoning.
Return whether n is a perfect square using binary search without sqrt.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: (16,)
Expected Output: True
Explanation: Perfect square.
Input: (14,)
Expected Output: False
Explanation: Not a square.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.