# Binary Search

## 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;

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

// Initialize values from input
value = 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;
}