If the number of serach termes become large, it would be better to use a StringBuilder. Otherwise, a new string will be allocated for each iteration.

I would consider to cache results:

	public string BinarySearchSetup(long[] data, long[] searchTerms)
	{
		var lowerBound = 0;
		var upperBound = data.Length - 1;

		var cache = new Dictionary<long, long>();
		var resultBuilder = new StringBuilder();
		for (var i = 0; i < searchTerms.Length; i++)
		{
			var searchTerm = searchTerms[i];
			long result;
			if (!cache.TryGetValue(searchTerm, out result))
			{
				result = BinarySearch(data, lowerBound, upperBound, searchTerm);
				cache.Add(searchTerm, result);
			}
			resultBuilder.Append(result);
			resultBuilder.Append(" ");
		}
		return resultBuilder.ToString();
	}