Skip to content

Find Number in Sorted Array

Level: L3 Topics: Binary Search, String Parsing

Problem Statement

You are given a sorted array of integers represented as a single string, with values separated by whitespace. There may be multiple spaces between values.

Write a function to find whether a target number exists in the array and return its index (or -1 if not found).

int findInSortedString(String s, int target)

Background & Constraints

  • The string contains integers separated by one or more spaces.
  • The integers are sorted in non-decreasing order.
  • The string can be very long (representing millions of numbers).
  • Leading and trailing whitespace may be present.
  • Numbers can be negative (prefixed with -).
  • You should aim for better than O(N) time complexity where N is the count of numbers.

Examples

Example 1:

s = "1  3  5   7  9  11"
target = 7
Answer: 3 (0-indexed position of 7)

Example 2:

s = "  2   4   6   8  "
target = 5
Answer: -1 (not found)

Example 3:

s = "-5  -3  0  2  10  100"
target = -3
Answer: 1

Example 4:

s = "42"
target = 42
Answer: 0

Hints & Common Pitfalls

  • Naive approach: Split the string by whitespace, parse all numbers into an array, then binary search. This is O(N) for parsing plus O(log N) for search. The parsing step dominates.

  • Binary search on the string directly: To avoid parsing the entire string, binary search on the character position. Jump to the middle of the string, find the nearest number boundary, parse that number, and decide which half to search.

  • Finding number boundaries: From a character position, scan left to find the start of the current number and right to find the end. Be careful with multi-space gaps — landing in a gap means you need to move to the next or previous number.

  • Common mistake: Incorrect handling of multiple consecutive spaces. Splitting on a single space produces empty strings that must be filtered.

  • Another pitfall: Negative numbers — make sure the - sign is included when parsing.

  • Edge cases: Empty string, single number, target smaller than all numbers, target larger than all numbers.

Follow-Up Questions

  1. True O(log N) search: Can you achieve O(log N) time (in terms of the count of numbers, not string length) without preprocessing? What assumptions about number sizes are needed?

  2. Count occurrences: If the array may contain duplicates, find the first and last occurrence of the target. How do you adapt the binary search?

  3. Memory-mapped file: If the string is stored in a file on disk and is too large for memory, how would you perform the binary search using file seeks? What is the I/O complexity?