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 ");
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
}
}

static int FindMaximum(int[] a, int low, int high)
{

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)
{
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;
}

}

static int BinarySearchDescendingOrder(int[] a, int low, int high, int key)
{
while (low <= high)
{
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;
}

}

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
```