/*

Code the function below to find the value in an array that matches its index.

If the array does not contain a value that matches its index, it should return -1.

*/

​

using System;

public class Program

{

    public static void Main()

    {

        var arrayWithMatch = new int[] { -40, -20, -1, 1, 2, 3, 4, 7, 9, 12, 13 };

        var arrayWithoutMatch = new int[] { -40, -20, -1, 1, 2, 3, 4, 8, 9, 12, 13 };

        Console.WriteLine(FindValueThatMatchesIndex(arrayWithMatch) == 7 ? "PASSED" : "FAILED");

        Console.WriteLine(FindValueThatMatchesIndex(arrayWithoutMatch) == -1 ? "PASSED" : "FAILED");

    }

    public static int FindValueThatMatchesIndex(int[] numbers)

    {

        var result = -1;

​

        result = IndexCompare(numbers, 0, numbers.Length - 1, (numbers.Length / 2));

​

        return result;

    }

​

    //binary search

    public static int IndexCompare(int[] numbers, int start, int end, int index)

    {

        if (numbers[index] == index)

            return index;

​

        //bottom half

        if (index < numbers[index])

        {

            var newIndex = ((index - start) / 2) + start;

            if (newIndex == index) //not found

                return -1;

            return IndexCompare(numbers, start, index, newIndex);

        }

​

        //top half

        if (index > numbers[index])

        {

            var newIndex = ((end - index)/2) + index;

            if (newIndex == index) //not found

                return -1;

            return IndexCompare(numbers, index, end, newIndex);

        }

​

        return -1;

    }

}