Search in a Sorted Array of Unknown Size

class ArrayReader;

class Solution {
  public:
  int findTarget(const ArrayReader& reader, int target) {
    if (reader.get(0) == target) return 0;

    // Establish search range
    int start = 0, end = 1;
    while (reader.get(end) < target) {
      start = end;
      end *= 2;
    }

    // Execute binary search
    int mid, value;
    while (start <= end) {
      mid = start + ((end - start) >> 1);
      value = reader.get(mid);

      if (value == target) return mid;
      if (value > target) end = mid - 1;
      else start = mid + 1;
    }

    // If target not found
    return -1;
  }
};

The provided C++ solution implements a method for searching a target value in a sorted array of unknown size using an ArrayReader interface. The binary search technique adapts to the unknown size by first determining an appropriate search range and then conducting the binary search.

Outline of the Solution:

• First, check if the target is at the initial position of the array.
• Start with a range defined by a start index of 0 and an end index of 1, then exponentially expand the end index until the value at end is greater than the target. This step determines the bounds for binary search.
• Proceed with a standard binary search:
  • Calculate the middle index using bit manipulation for efficient division by 2.
  • Retrieve the value at the middle index.
  • Compare the retrieved value with the target.
    • If equal, return the middle index as the target's position.
    • If the value is greater than the target, adjust the end index to narrow down the search range.
    • If the value is less than the target, adjust the start index to explore the range with potentially larger values.
• If the loop exits without finding the target, return -1 indicating that the target is not present in the array.

Use the exponential and binary search combination wisely to manage searches efficiently in large datasets or arrays where the size is not directly known. This approach minimizes the number of accesses to the array, which is crucial if every access is costly.

class Solution {
  public int findInArray(ArrayReader reader, int target) {
    if (reader.get(0) == target) return 0;

    // Initialize search bounds
    int start = 0, end = 1;
    while (reader.get(end) < target) {
      start = end;
      end <<= 1;
    }

    // Perform binary search
    int mid, value;
    while (start <= end) {
      mid = start + ((end - start) >> 1);
      value = reader.get(mid);

      if (value == target) return mid;
      if (value > target) end = mid - 1;
      else start = mid + 1;
    }

    // Target not found
    return -1;
  }
}

The provided Java solution implements a search mechanism for finding a target value in a sorted array where the size of the array is unknown. Follow these main points outlined in the code to understand the search process:

• Initial Check: The code begins with a quick check to see if the target is at the first position of the array. If found, the position 0 is immediately returned.

• Bounds Initialization: To accommodate the unknown size, the solution initializes two pointers, start and end, marking the boundaries of the search interval. The end is initially set to 1, doubling with each step until it finds a value that is no smaller than the target. This step ensures that the target, if present, lies between start and end.

• Binary Search Implementation: Once the boundary is determined where the target value may exist, a standard binary search is executed within those bounds.

  • The midpoint (mid) and its corresponding value (value) are recalculated in each iteration.
  • If value matches the target, the index mid is returned.
  • If value is greater than the target, the end boundary is adjusted, narrowing the search to the lower half.
  • Conversely, if value is less, the search shifts to the upper half by adjusting the start.

• Return Condition: If the target is not located within the search bounds, -1 is returned, indicating absence of the target in the array.

This approach efficiently narrows down the potential search area even in an array with unknown size, leveraging the properties of sorted data and applying a logarithmic search algorithm to find the target effectively.