ArraysUtil.java

package com.example.alg;

public final class ArraysUtil {
  private ArraysUtil() {}

  public static int binarySearch(int[] a, int target) {
    int l = 0, r = a.length - 1;
    while (l <= r) {
      int m = l + (r - l) / 2;
      if (a[m] == target) return m;
      if (a[m] < target) l = m + 1; else r = m - 1;
    }
    return -1;
  }

  public static int[] twoSumSorted(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i < j) {
      int sum = a[i] + a[j];
      if (sum == target) return new int[]{i, j};
      if (sum < target) i++; else j--;
    }
    return new int[]{-1, -1};
  }

  public static int[] prefixSums(int[] a) {
    int[] p = new int[a.length + 1];
    for (int i = 0; i < a.length; i++) p[i + 1] = p[i] + a[i];
    return p;
  }
}