> For the complete documentation index, see [llms.txt](https://howardyangemail.gitbook.io/decode-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://howardyangemail.gitbook.io/decode-leetcode/binary-search.md).

# Binary Search

#### [704. Binary Search](https://leetcode.com/problems/binary-search/)

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Python" %}

```python
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left + 1 < right:
            mid = int(left + (right - left) / 2)
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid
            else:
                right = mid
        if nums[left] == target:
            return left
        if nums[right] == target:
            return right
        return -1
```

{% endtab %}
{% endtabs %}

#### [278. First Bad Version](https://leetcode.com/problems/first-bad-version/)

Find first "`T`" in the array, when meet the situation below, still move L pointer:

`#  F  F  F   T  T  T`

`# [1, 2, 10, 11.., n]`

```python
    def firstBadVersion(self, n):
        L = 1
        R = n
        while L < R:
            mid = (L + R) // 2
            if isBadVersion(mid) :
                R = mid
            else: 
                L = mid + 1
        return L
```

#### [162. Find Peak Element](https://leetcode.com/problems/find-peak-element/) & [852. Peak Index in a Mountain Array](https://leetcode.com/problems/peak-index-in-a-mountain-array/)

when `nums[mid] > nums[mid - 1]` means it is on upslope, move L pointer. Otherwise move R pointer.

```python
def findPeakElement(self, nums: List[int]) -> int:
    L = 0
    R = len(nums)
    while L < R:
        mid = (L + R) // 2
        if mid < len(nums) - 1 and nums[mid + 1] >= nums[mid]:
            L = mid + 1
        else :
            R = mid
    return L
```

#### [34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

Find the first position and the last position separately. Treat differently as `nums[mid] == target`

```java
public int[] searchRange(int[] nums, int target) {
    if (nums == null || nums.length == 0 || target > nums[nums.length - 1]) {
        return new int[]{-1, -1};
    }
    int left = binarySearchFirst(nums, 0, nums.length - 1, target);
    int right = binarySearchLast(nums, 0, nums.length - 1, target);
    return left == -1 ? new int[]{-1, -1} : new int[]{left, right};
}

private int binarySearchFirst(int[] nums, int left, int right, int target) {
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid;
        }
    }
    if (nums[left] == target) return left;
    if (nums[right] == target) return right;
    return -1;
}

private int binarySearchLast(int[] nums, int left, int right, int target) {
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid;
        } else {
            right = mid;
        }
    }
    if (nums[right] == target) return right;
    if (nums[left] == target) return left;
    return -1;
}
```

#### [33. Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)

Use right most digit as a `pivot` to determine if mid is on the lower side or the higher side, then determine the position of target to move the pointers.

```python
def search(self, nums: List[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    L = 0
    R = len(nums) - 1
    pivot = nums[R]
    
    while L + 1 < R:
        mid = (L + R) // 2
        if nums[mid] <= pivot:
            if target <= pivot and target >= nums[mid]:
                L = mid
            else :
                R = mid
        else :
            if target > pivot and target < nums[mid]:
                R = mid
            else:
                L = mid
    if nums[L] == target :
        return L
    if nums[R] == target:
        return R
    return -1
```

#### [81. Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/)

When `nums[mid] == nums[L] and nums[mid] == nums[R]` means all three pointers are on same level. Compare `target vs nums[R],` check if `nums[mid]` is in between, or on the opposite side.

```python
def search(self, nums: List[int], target: int) -> bool:
    L = 0
    R = len(nums) - 1
    if len(nums) == 0:
        return False
    while L + 1 < R:
        mid = (L + R) // 2
        if nums[mid] == target:
            return True
        if nums[mid] == nums[L] and nums[mid] == nums[R]:
            L += 1
            R -= 1
        elif target <= nums[R]:
            if nums[mid] > target and nums[mid] <= nums[R]:
                R = mid
            else:
                L = mid
        else:
            if nums[mid] < target and nums[mid] > nums[R]:
                L = mid
            else:
                R = mid
    if nums[L] == target or nums[R] == target:
        return True
    return False
```

#### [153. Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)

Use right most element as pivot to determine the direction of the search. If `nums[mid]` less and equal to `pivot`, then move `R` to `mid`. Otherwise move `L` to `mid`.

```python
    def findMin(self, nums: List[int]) -> int:
        L = 0
        R = len(nums) - 1
        pivot = nums[len(nums) - 1]
        while L + 1 < R:
            mid = (L + R) // 2
            if nums[mid] > pivot:
                L = mid
            else:
                R = mid
        return min(nums[L], nums[R])
```

#### [702. Search in a Sorted Array of Unknown Size](https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/solution/)

Define boundaries by expanding right pointer. To keep logarithmic time complexity, let's extend it twice as far: `right = right * 2`. Then binary search.

```python
    def search(self, reader, target):
        R = 1
        while reader.get(R) <= target:
            R *= 2
        L = 0
        while L + 1 < R:
            mid = (L + R) // 2
            if reader.get(mid) == target:
                return mid
            if reader.get(mid) < target:
                L = mid
            else:
                R = mid
        if reader.get(L) == target:
            return L
        if reader.get(R) == target:
            return R
        return -1
```

Another solution (if getNumber() API is provided):

```java
  public boolean binarysearch(long target) {
    long start = 0;
    long end = 1;
    while (getNumber(end) <= target && end < Long.MAX_VALUE / 2) {
      end *= 2;
    }
    if (getNumber(end) < target) {
      end = Long.MAX_VALUE;
    }
    while (start + 1 < end) {
      long mid = start + (end - start) / 2;
      if (getNumber(mid) == target) {
        return true;
      } else if (getNumber(mid) < target) {
        start = mid;
      } else {
        end = mid;
      }
    }
    return getNumber(start) == target || getNumber(end) == target;
  }
```

#### [50. Pow(x, n)](https://leetcode.com/problems/powx-n/)

`2 ^ 10 = 4 ^ 5 = 16 ^ 2 * 4`&#x20;

*T: O(logn)  S: O(1)*

```java
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        if (n == 1) return x;
        int i = Math.abs(n);
        double res = 1.0;
        while (i != 0) {
            if (i % 2 != 0) {
                res *= x; 
            }
            x *= x;
            i /= 2;
        }
        return n < 0 ? 1.0 / res : res;
    }
```

#### [540. Single Element in a Sorted Array](https://leetcode.com/problems/single-element-in-a-sorted-array/)

For example, in `[1,1,3,3,4,4,5,8,8]`, elements before `5` keep \[even, odd] pattern, to make sure that even and odd number sequence. The elements after `5` break this sequence. In this case,  we can determine the target is on the left or the right side of pivot.&#x20;

```python
    def singleNonDuplicate(self, nums: List[int]) -> int:
        L = 0
        R = len(nums) - 1
        while L < R:
            mid = (L + R) // 2
            if mid % 2 == 0 and mid < len(nums) - 1 and nums[mid + 1] == nums[mid]:
                L = mid + 1
            elif mid % 2 == 1 and mid > 0 and nums[mid - 1] == nums[mid]:
                L = mid + 1
            else:
                R = mid
        return nums[L]
```

#### [1060. Missing Element in Sorted Array](https://leetcode.com/problems/missing-element-in-sorted-array/)

`nums[mid] - nums[left]` is the number difference on array, `mid - left`is the difference of indices. The difference `diff` between those two numbers can give you how close are we reaching out to `k`.

The `k` needs to decrement by `diff` when moving left pointer, as `k` is from the beginning.&#x20;

The result is `nums[left] + k`. However the number may exceed right so the result is `nums[left] + k + 1` in that situation.

```java
    public int missingElement(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int diff = nums[mid] - nums[left] - (mid - left);
            if (diff < k) {
                left = mid;
                k -= diff;
            } else {
                right = mid;
            }
        }
        if (nums[left] + k >= nums[right]) return nums[left] + k + 1;
        return nums[left] + k;
    }
```

#### [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)

`dp` is an array storing the smallest tail of all increasing subsequences with length `i+1` in `dp[i]`.\
For example, say we have `nums = [4,5,6,3]`, then all the available increasing subsequences are:

* len = 1   :      \[4], \[5], \[6], \[3]   => tails\[0] = 3
* len = 2   :      \[4, 5], \[5, 6]       => tails\[1] = 5
* len = 3   :      \[4, 5, 6]            => tails\[2] = 6

We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

Each time we only do one of the two:

* *if x is larger than all tails, append it, increase the size by 1*
* *if dp\[i-1] < x <= dp\[i], update dp\[i]*

*T*: O(nlogn)

```java
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    int size = 0;
    for (int num : nums) {
        int L = 0, R = size;
        while (L < R) {
            int mid = L + (R - L) / 2;
            if (res[mid] < num) {
                L = mid + 1;
            } else {
                R = mid;
            }
        }
        res[L] = num;
        if (L == size) size++;
    }
    return size;
}
```

#### [911. Online Election](https://leetcode.com/problems/online-election/)

**Count the votes and derive the winner that that time**. When querying, store the results in a **TreeMap** to get the results. Otherwise we can store by using an **array** and use **binary search** to find the answer.

{% tabs %}
{% tab title="TreeMap" %}

```java
TreeMap<Integer, Integer> results;
public TopVotedCandidate(int[] persons, int[] times) {
    Map<Integer, Integer> votes = new HashMap<>();
    results = new TreeMap<>();
    int n = persons.length;
    int max = 0, maxperson = -1;
    for (int i = 0; i < n; i++) {
        votes.put(persons[i], votes.getOrDefault(persons[i], 0) + 1);
        if (votes.get(persons[i]) >= max) {
            max = votes.get(persons[i]);
            maxperson = persons[i];
        }
        results.put(times[i], maxperson);
    }
}

public int q(int t) {
    int key = results.get(t) != null ? t
                                     : results.lowerKey(t);
    return results.get(key);
}
```

{% endtab %}

{% tab title="Binary Search" %}

```java
List<Node> list = new ArrayList<>();
public TopVotedCandidate(int[] persons, int[] times) {
    Map<Integer, Integer> votes = new HashMap<>();
    int n = persons.length;
    int max = 0, maxperson = -1;
    for (int i = 0; i < n; i++) {
        votes.put(persons[i], votes.getOrDefault(persons[i], 0) + 1);
        if (votes.get(persons[i]) >= max) {
            max = votes.get(persons[i]);
            maxperson = persons[i];
        }
        list.add(new Node(times[i], maxperson));
    }
}

public int q(int t) {
    int left = 0, right = list.size() - 1;
    if (t > list.get(right).time) {
        return list.get(right).maxperson;
    }
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (list.get(mid).time == t) return list.get(mid).maxperson;
        if (list.get(mid).time < t) {
            left = mid;
        } else {
            right = mid;
        }
    }
    if (list.get(right).time == t) return list.get(right).maxperson;
    return list.get(left).maxperson;
}

class Node {
    int time;
    int maxperson;
    Node(int t, int p) {
        this.time = t;
        this.maxperson = p;
    }
}
```

{% endtab %}
{% endtabs %}

#### [528. Random Pick with Weight](https://leetcode.com/problems/random-pick-with-weight/)

Store the array to prefix sum and randomly get an integer between range 0 and max. Use binary search to get the index of that integer is presum.

```java
int[] w;
Random rand;
public Solution(int[] w) {
    this.w = w;
    for (int i = 1; i < w.length; i++) {
        w[i] += w[i - 1];
    }
    this.rand = new Random();
}

public int pickIndex() {
    int index = rand.nextInt(w[w.length - 1]) + 1;
    int L = 0, R = w.length - 1;
    while (L < R) {
        int mid = L + (R - L) / 2;
        if (w[mid] == index) return mid;
        if (w[mid] < index) {
            L = mid + 1;
        } else {
            R = mid;
        }
    }
    return L;
}
```

#### [4. Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/)

We can use **Binary Search** to find a median of two sorted array. The index i in the first array has to follow this relation as **`i + j = (len1 + len2) / 2`** (Actually it is  `i + j - 1= (len1 + len2 + 1) / 2`). Therefore, use binary search to find the position which **`nums1[i] >= nums2[j - 1]`**.&#x20;

You will have i, j. Before return, determine if any of the indices are out of bound. Keep the boundary elements by choosing one value between i and j. If is odd total length, only pick one element as median, otherwise get the average of those two boundary elements.

```java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len1 = nums1.length, len2 = nums2.length;
    if (len1 > len2) return findMedianSortedArrays(nums2, nums1);
    int len = (len1 + len2 + 1) / 2;
    int left = 0, right = len1;
    while (left < right) {
        int m1 = left + (right - left) / 2;
        int m2 = len - m1;
        if (nums1[m1] < nums2[m2 - 1]) {
            left = m1 + 1;
        } else {
            right = m1;
        }
    }
    int m1 = left, m2 = len - m1;
    int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],
                      m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
    if ((len1 + len2) % 2 == 1) return c1;
    int c2 = Math.min(m1 >= len1 ? Integer.MAX_VALUE : nums1[m1],
                      m2 >= len2 ? Integer.MAX_VALUE : nums2[m2]);
    return (c1 + c2) / 2.0;
}
```

#### [1095. Find in Mountain Array](https://leetcode.com/problems/find-in-mountain-array/)

![3 binary searches](/files/-MIZzojuv5psXTzKTMSZ)

```java
public int findInMountainArray(int target, MountainArray A) {
    int left = 0, right = A.length() - 1;
    // Find the peak index
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (A.get(mid) < A.get(mid + 1)) {
            left = mid + 1;
        } else { 
            right = mid;
        }
    }
    int peak = left;
    
    // Binary search on increasing subarray
    left = 0;
    right = peak;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (A.get(mid) < target) {
            left = mid + 1;
        } else if (A.get(mid) > target) { 
            right = mid - 1;
        } else {
            return mid;
        }
    }
    
    // Binary search on decreasing subarray
    left = peak;
    right = A.length() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (A.get(mid) < target) {
            right = mid - 1;
        } else if (A.get(mid) > target) { 
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}
```

#### [Binary Searchable Elements](https://leetcode.com/discuss/interview-question/879774/Google-or-Onsite-or-Binary-Searchable-Elements)

Binary search is a search algorithm usually used on a sorted sequence to quickly find an element with a given value. In this problem we will evaluate how binary search performs on data that isn't necessarily sorted. An element is said to be binary searchable if an element can be found provided the pivot is chosen everytime as the **middle element** - like in a regular binary search.\
We need to find total number of elements which are binary searchable.

**Example 1:**

> \[2, 1, 3, 4, 6, 5] - 3 is searchable, 2 is searchable, 1 not searchable, 6 is searchable, 4 is seachable, 5 is not searchable&#x20;
>
> Output: 4

**Example 2:**

> Input: \[1, 3, 2]
>
> Output: 2
>
> Explanation: 3 and 1 are searchable - you look for 3 - find it in the middle, look for 1 - you search the left half....search for 2, you look for it in the left half but didn't find.

Pretend the array is a binary search tree, DFS/BFS all pivot elements and keep track of lower and upper bound for the left and right children. The idea is to figure out how many middle elements in the given start to end range is properly positioned compared to previous middle element - so that they can be binary searchable in the given array.

```java
public int getSearchableCount(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    return getSearchableCount(arr, 0, arr.length-1, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private int getSearchableCount(int[] arr, int start, int end, int lowerBound, int upperBound) {
    if (start > end) {
        return 0;
    }
    int mid = (start + end) / 2;
    int count = 0;
    if (arr[mid] >= lowerBound && arr[mid] <= upperBound) count ++;
    return count + getSearchableCount(arr, start, mid-1, lowerBound, Math.min(arr[mid], upperBound)) +
            getSearchableCount(arr, mid + 1, end, Math.max(arr[mid], lowerBound), upperBound);
}

public static void main(String[] args) {
    BinarySearchable obj = new BinarySearchable();
    System.out.println(obj.getSearchableCount(new int[]{2, 1, 3, 4, 6, 5}));
    System.out.println(obj.getSearchableCount(new int[]{1, 3, 2}));
    System.out.println(obj.getSearchableCount(new int[]{1, 2, 2, 3}));
    System.out.println(obj.getSearchableCount(new int[]{4, 9, 5, 1, 1}));
}
```

[3453. Separate Squares I](https://leetcode.com/problems/separate-squares-i/)

```typescript
function separateSquares(squares: number[][]): number {
  let lo: number = Number.POSITIVE_INFINITY; // initial lower bound
  let hi: number = Number.NEGATIVE_INFINITY; // initial upper bound

  for (const [x, y, l] of squares) {
    lo = Math.min(lo, y - l);
    hi = Math.max(hi, y + l);
  }

  const eps: number = 1e-5; // tolerance level

  while (hi - lo > eps) {
    const mid = (lo + hi) / 2;
    if (isAboveLine(mid, squares)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }

  return (lo + hi) / 2;
}

function isAboveLine(line: number, squares: number[][]): boolean {
  let above = 0;
  let below = 0;

  for (const [x, y, l] of squares) {
    const top = y + l;
    if (line <= y) {
      // Entire square above line
      above += l * l;
    } else if (line >= top) {
      // Entire square below line
      below += l * l;
    } else {
      // Partial square, line cuts inside square
      const heightAbove = top - line;
      const heightBelow = line - y;
      above += heightAbove * l;
      below += heightBelow * l;
    }
  }

  return above > below;
}

```