Iterative approach

BinaryIsRight.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = new Random();
            for (int i = 0; i < 10; i++)
            {
                // generate random assortment of items
                var items = GenerateItems().ToArray();
                var prize = r.Next(items.First(), items.Last());

                // try to find our best guess using binary search
                var bestGuess = Search(items, prize);
                // get actual best guess iteratively
                var expectedBestGuess = IterativeSearch(items, prize);

                // display
                Console.WriteLine("Prize = {0}", prize);
                if (bestGuess > 0)
                    Console.WriteLine("[{0}] = {1} Found", bestGuess, items[bestGuess]);

                Console.WriteLine("[{0}] = {1} Expected", expectedBestGuess, items[expectedBestGuess]);
                Console.WriteLine("===========");
            }

            if (Debugger.IsAttached)
            {
                Console.WriteLine("Press any key to quit");
                Console.Read();
            }
        }

        private static int Search(int[] items, int prize)
        {
            int min = 0;
            int max = items.Length - 1;

            while (max > min)
            {
                // calculate midpoint of section of array we are within range
                int midpoint = (min + max) / 2;

                // check for perfect match
                if (items[midpoint] == prize)
                {
                    return midpoint;
                }
                else if (items[midpoint] < prize)
                {
                    min = midpoint + 1;
                }
                else if (items[midpoint] > prize)
                {
                    max = midpoint - 1;
                }

                // since we aren't guaranteed to have exact match, when filtered down to 2 candidates, pick highest
                // that isn't higher than the prize
                if ((max - min) < 2)
                {
                    if (items[max] <= prize) return max;
                    if (items[min] <= prize) return min;
                }
            }


            return -1;
        }

        private static IEnumerable<int> GenerateItems()
        {
            var random = new Random();
            var current = 0;
            for (int i = 0; i < 400000; i++)
            {
                yield return ++current;

                current += random.Next(0, 11);
            }
        }

        private static int IterativeSearch(int[] items, int prize)
        {
            for (int i = 0; i < items.Length; i++)
            {
                if (items[i] > prize)
                    return i - 1;
            }

            return -1;
        }
    }
}