Introcs.cs.princeton.edu

Problem Description

Given a 1-indexed array of integers that is sorted in non-decreasing order, find two numbers such that they add up to a target number.

Solution: Linear Scan with Binary Search

#binary-search

At its core, the problem is a binary search one. Given \(a\), find \(b = t - a\) in the right side of array. If \(a > \lfloor t / 2 \rfloor\), then there is no possible \(b\) to the right because \(b \ge a\) and \(2a > t\).