Skip to content

Latest commit

 

History

History
8 lines (8 loc) · 690 Bytes

note0702.md

File metadata and controls

8 lines (8 loc) · 690 Bytes
Raw

Leetcode 702. Search in a Sorted Array of Unknown Size

  • Type: Binary search + Bit
  • Approach:
    1. The basic intuition to solve the problem is to use binary search. However, we don't know the size of the array, which means that we have to find the upper bound firstly.
    2. The way to find the upper bound is that we can use Bit to find use a hi value to compare with the target. We initially set the value of hi is 1, and if hi value is less than target, then we move the 1 bit to the left. In this way, we can quickly find the upper bound by exponential increasing.
  • Complexity:
    • Time: O(nlogn)
    • Space: O(1)