Problem:

Given $N (1 \le N \le 100000)$ values of distances $d_i$ between two points $p_i$ and $p_{i+1}$, answer $Q (1 \le Q \le 100000)$ queries of the form “What point $p$ is at or directly beneath some distance $d$?”

(Note: $p_0$ is at distance $0$)

Input (file.in):

Line $1$: Two integers, $N$ and $Q$.
Lines $2 \ldots N+1$: One integer, $d_i$.

Output (file.out):

Line $1 \ldots Q$: The answer to the question “What point $p$ is at or directly beneath some distance $d$?”.

Solution:

(Note: My solution may be off by one from the problem statement… off by one errors are very annoying…)

/*
* Example Binary Search
* Albert Gural
*/

#include <fstream> 		//File input/output

using namespace std;
FILE *fin  = fopen("file.in",  "r");
FILE *fout = fopen("file.out", "w");
// N is # of elements, Q is queries
// value is a sorted array of values
// on which to binary search.
int N, Q, a, value[100005];

int main () {
	fscanf(fin, "%d %d", &N, &Q);

	// Initialize values from input
	value[0] = 0;
	for(int i = 1; i <= N; i++) {
		fscanf(fin, "%d", &a);
		value[i] = value[i - 1] + a;
	}

	// Binary Search on each query.
	for(int i = 0; i < Q; i++) {
		fscanf(fin, "%d", &a);
		int low = 0, high = N, mid = (low + high + 1) / 2;

		// While we haven't found the element,
		// choose low or high based on where query is
		// relative to mid.
		while(value[mid] != a && high - low > 1) {
			if(value[mid] < a) low = mid;
			else high = mid;
			mid = (low + high + 1) / 2;
			if(value[low] == a) {
				mid = low;
				break;
			}
		}

		// Print the location.
		fprintf(fout, "%d\n", mid);
	}
	return 0;
}