The following program determines if a given integer exists in a bitonic array. An array is bitonic if it contains an increasing sequence of integers followed immediately by a decreasing sequence of integers. The program uses 3lgN compares in the worst case.

Examples of 3-element bitonic arrays:

             X        X      X
     X      X X      X X    X X
    X X    X   X    X          X

The program:

using System;
using System.Diagnostics;

namespace ConsoleTest
{
    class Program
    {
        private static Stopwatch stopwatch = new Stopwatch();
        private static Random rnd = new Random();
        private static int delayInMilisecond = 100;
        private static bool runWorseCaseScenario = false;

        // 'compares' is the number of iterations in loops and the number of calls 
        // to the recursive method.
        private static int compares = 0; 

        static void Main(string[] args)
        {
            Console.Write("[R] - random case scenario, [W] - worse case scenario ");
            char key = Console.ReadKey().KeyChar;
            runWorseCaseScenario = (key == 'W' || key == 'w');
            Console.WriteLine();

            double prev = RunTimeTrial(125);
            for (int N = 250; true; N += N)
            {
                double time = RunTimeTrial(N);

                // We use log2 because the method uses binary search.
                Console.WriteLine("Size: {0}   Time: {1:F2} sec   Ratio: {2:F2}   3ln(N): {3:F2}   compares: {4}\n", N, time, time / prev, 3 * Math.Log(N, 2), compares);
                prev = time;
            }
        }

        static double RunTimeTrial(int N)
        {
            if (N < 3)
                throw new ArgumentException("The size of the array should be greater than 3.");

            int[] a = new int[N];

            int n = 1;

            // Populate the array with a bitonic sequence.

            // Determine the index of the maximum. 
            // Exclude the first and the last element from being the maximum.
            int max = (
                runWorseCaseScenario ?
                a.Length / 4 : // max is in the 1/4th of the sequence; if it was in the middle, the time to find max would be const
                rnd.Next(1, a.Length - 2));

            // Populate the ascending part with odd numbers.
            for (int i = 0; i <= max; ++i)
            {
                a[i] = n;
                n += 2;
            }

            n -= 3;

            // Populate the descending part with even numbers
            for (int i = max + 1; i < a.Length; ++i)
            {
                a[i] = n;
                n -= 2;
            }

            // Pick a value to find.
            int key = (
                runWorseCaseScenario ?
                a[a.Length - 1] : // the value to find is the last element
                a[rnd.Next(0, a.Length)]);

            stopwatch.Reset();
            stopwatch.Start();

            compares = 0;
            FindValue(a, key);

            return (stopwatch.ElapsedMilliseconds / 1000.0);
        }


        static void FindValue(int[] a, int key)
        {
            int max = FindMaximum(a, 0, a.Length - 1);

            int left = BinarySearchAscendingOrder(a, 0, max, key);
            if (left != -1)
                Console.WriteLine("Element found: a[{0}] = {1}", left, a[left]);
            else
            {
                int right = BinarySearchDescendingOrder(a, max + 1, a.Length - 1, key);
                if (right != -1)
                    Console.WriteLine("Element found: a[{0}] = {1}", right, a[right]);
                else
                    Console.WriteLine("Element not found.");
            }
        }

        static int FindMaximum(int[] a, int low, int high)
        {
            System.Threading.Thread.Sleep(delayInMilisecond); // just for testing!

            int middle = (low + high) / 2;

            if (middle == 0) middle++;
            if (middle == a.Length) middle--;

            compares++;

            if (a[middle] > a[middle - 1] && a[middle] > a[middle + 1])
                return middle;

            if (a[middle - 1] < a[middle])
                low = middle + 1; // go up
            else
                high = middle - 1; // go down

            return FindMaximum(a, low, high);
        }

        // BinarySearch finds the index of an element in the sub-array a[low,high] that has 
        // the value 'key'. The array 'a' must be sorted.
        static int BinarySearchAscendingOrder(int[] a, int low, int high, int key)
        {
            while (low <= high)
            {
                System.Threading.Thread.Sleep(delayInMilisecond); // just for testing!
                compares++;

                int middle = low + (high - low) / 2;

                if (key < a[middle])
                    high = middle - 1;
                else if (key > a[middle])
                    low = middle + 1;
                else
                    return middle;
            }

            return -1; // the 'key' value not found
        }

        static int BinarySearchDescendingOrder(int[] a, int low, int high, int key)
        {
            while (low <= high)
            {
                System.Threading.Thread.Sleep(delayInMilisecond); // just for testing!
                compares++;

                int middle = low + (high - low) / 2;

                if (key < a[middle])
                    low = middle + 1;
                else if (key > a[middle])
                    high = middle - 1;
                else
                    return middle;
            }

            return -1; // the 'key' value not found
        }

        static void TestFindMaximum()
        {
            int[] a1 = { 1, 5, 2 };
            int index1 = FindMaximum(a1, 0, a1.Length - 1);
            Console.WriteLine("Maximum: a[{0}] = {1}", index1, a1[index1]);

            int[] a2 = { 1, 3, 5, 2 };
            int index2 = FindMaximum(a2, 0, a2.Length - 1);
            Console.WriteLine("Maximum: a[{0}] = {1}", index2, a2[index2]);

            int[] a3 = { 1, 5, 4, 2 };
            int index3 = FindMaximum(a3, 0, a3.Length - 1);
            Console.WriteLine("Maximum: a[{0}] = {1}", index3, a3[index3]);

            int[] a4 = { 1, 3, 5, 4, 2 };
            int index4 = FindMaximum(a4, 0, a4.Length - 1);
            Console.WriteLine("Maximum: a[{0}] = {1}", index4, a4[index4]);

            int[] a5 = { 1, 5, 4, 2, 0 };
            int index5 = FindMaximum(a5, 0, a5.Length - 1);
            Console.WriteLine("Maximum: a[{0}] = {1}", index5, a5[index5]);

            int[] a6 = { 1, 2, 3, 5, 4 };
            int index6 = FindMaximum(a6, 0, a6.Length - 1);
            Console.WriteLine("Maximum: a[{0}] = {1}", index6, a6[index6]);

            int[] a7 = { 18, 23, 20, 8, 3, 2, 1, -9 };
            int index7 = FindMaximum(a7, 0, a7.Length - 1);
            Console.WriteLine("Maximum (23): a[{0}] = {1}", index7, a7[index7]);

            int[] a8 = { 6, 8, 12, 9, 4, 1, -5, -6, -10, -23, -56, -78, -90, -91 };
            int index8 = FindMaximum(a8, 0, a8.Length - 1);
            Console.WriteLine("Maximum (12): a[{0}] = {1}", index8, a8[index8]);

            int[] a9 = { 1, 3, 7, 14, 15, 17, 20, 25, 29, -7 };
            int index9 = FindMaximum(a9, 0, a9.Length - 1);
            Console.WriteLine("Maximum (29): a[{0}] = {1}", index9, a9[index9]);

            int[] a10 = { 1, 3, 7, 14, 15, 17, 20, 19, 10, -5 };
            int index10 = FindMaximum(a10, 0, a10.Length - 1);
            Console.WriteLine("Maximum (20): a[{0}] = {1}", index10, a10[index10]);
        }

        static void TestFindValue()
        {
            int[] a1 = { 1, 5, 2 };
            FindValue(a1, 1);
            FindValue(a1, 5);
            FindValue(a1, 2);
            Console.WriteLine();

            int[] a2 = { 1, 3, 5, 2 };
            FindValue(a2, 1);
            FindValue(a2, 3);
            FindValue(a2, 5);
            FindValue(a2, 2);
            Console.WriteLine();

            int[] a3 = { 1, 5, 4, 2 };
            FindValue(a3, 1);
            FindValue(a3, 5);
            FindValue(a3, 4);
            FindValue(a3, 2);
            Console.WriteLine();

            int[] a4 = { 1, 3, 5, 4, 2 };
            FindValue(a4, 1);
            FindValue(a4, 3);
            FindValue(a4, 5);
            FindValue(a4, 4);
            FindValue(a4, 2);
            Console.WriteLine();

            int[] a5 = { 18, 23, 20, 8, 3, 2, 1, -9 };
            FindValue(a5, 18);
            FindValue(a5, 23);
            FindValue(a5, 20);
            FindValue(a5, 8);
            FindValue(a5, 3);
            FindValue(a5, 2);
            FindValue(a5, 1);
            FindValue(a5, -9);
            Console.WriteLine();

            int[] a = { 6, 8, 12, 9, 4, 1, -5, -6, -10, -23, -56, -78, -90, -91 };
            FindValue(a, 6);
            FindValue(a, 8);
            FindValue(a, 12);
            FindValue(a, 9);
            FindValue(a, 4);
            FindValue(a, 1);
            FindValue(a, -5);
            FindValue(a, -6);
            FindValue(a, -10);
            FindValue(a, -23);
            FindValue(a, -56);
            FindValue(a, -78);
            FindValue(a, -90);
            FindValue(a, -91);
        }
    }
}

Sample output:

[R] - random case scenario:

Element found: a[17] = -28
Size: 250   Time: 1.80 sec   Ratio: 1.26   3ln(N): 23.90   compares: 16

Element found: a[35] = 71
Size: 500   Time: 1.80 sec   Ratio: 1.00   3ln(N): 26.90   compares: 16

Element found: a[270] = -286
Size: 1000   Time: 2.70 sec   Ratio: 1.50   3ln(N): 29.90   compares: 24

Element found: a[170] = 341
Size: 2000   Time: 2.43 sec   Ratio: 0.90   3ln(N): 32.90   compares: 22

Element found: a[2451] = 2616
Size: 4000   Time: 3.64 sec   Ratio: 1.50   3ln(N): 35.90   compares: 33

Element found: a[7808] = 4950
Size: 8000   Time: 3.94 sec   Ratio: 1.08   3ln(N): 38.90   compares: 36

Element found: a[10266] = 4286
Size: 16000   Time: 4.45 sec   Ratio: 1.13   3ln(N): 41.90   compares: 40

Element found: a[19344] = -34198
Size: 32000   Time: 4.23 sec   Ratio: 0.95   3ln(N): 44.90   compares: 39

Element found: a[11496] = 22993
Size: 64000   Time: 3.13 sec   Ratio: 0.74   3ln(N): 47.90   compares: 28
[W] - worse case scenario

Element found: a[249] = -248
Size: 250   Time: 2.11 sec   Ratio: 1.10   3ln(N): 23.90   compares: 21

Element found: a[499] = -496
Size: 500   Time: 2.31 sec   Ratio: 1.09   3ln(N): 26.90   compares: 23

Element found: a[999] = -996
Size: 1000   Time: 2.61 sec   Ratio: 1.13   3ln(N): 29.90   compares: 26

Element found: a[1999] = -1996
Size: 2000   Time: 2.91 sec   Ratio: 1.12   3ln(N): 32.90   compares: 29

Element found: a[3999] = -3996
Size: 4000   Time: 3.21 sec   Ratio: 1.10   3ln(N): 35.90   compares: 32

Element found: a[7999] = -7996
Size: 8000   Time: 3.52 sec   Ratio: 1.09   3ln(N): 38.90   compares: 35

Element found: a[15999] = -15996
Size: 16000   Time: 3.82 sec   Ratio: 1.09   3ln(N): 41.90   compares: 38

Element found: a[31999] = -31996
Size: 32000   Time: 4.12 sec   Ratio: 1.08   3ln(N): 44.90   compares: 41

Element found: a[63999] = -63996
Size: 64000   Time: 4.42 sec   Ratio: 1.07   3ln(N): 47.90   compares: 44