CSharp · Console
using System;
//A cloud, a cloud can be classified based on it's type.
//There are 10 different cloud types.
public class Cloud : IComparable<Cloud>, IEquatable<Cloud>
{
public CloudType Type
{
get;
set;
}
public Cloud(CloudType type)
{
Type = type;
}
public int CompareTo(Cloud obj)
{
if ((int)this.Type == (int)obj.Type)
return 0;
if ((int)this.Type < (int)obj.Type)
return -1;
if ((int)this.Type > (int)obj.Type)
return 1;
return 1;
}
public enum CloudType
{
Level10,
Level20,
Level30,
Level40,
Level50,
Level60,
Level70,
Level80,
Level90,
Level100
}
public bool Equals(Cloud other)
{
if (ReferenceEquals(null, other))
return false;
if (ReferenceEquals(this, other))
return true;
return (int)Type == (int)other.Type;
}
public override bool Equals(object obj)
{
if (ReferenceEquals(null, obj))
return false;
if (ReferenceEquals(this, obj))
return true;
if (obj.GetType() != this.GetType())
return false;
return Equals((Cloud)obj);
}
public override int GetHashCode()
{
return (int)Type;
}
}
class Program
{
//Generic implementation of the binary search algorithm using a recursive approach
static int RecursiveBinarySearch<T>(T[] array, T target, int? mostLeftIndex = null, int? mostRightIndex = null)
where T : IComparable<T>, IEquatable<T>
{
//Initialize the state of the indexes that correspond to the first and last available indexes in the array or sub-array.
if (!mostLeftIndex.HasValue)
mostLeftIndex = 0;
if (!mostRightIndex.HasValue)
mostRightIndex = array.Length - 1;
//If one of the indexes is in a situation like 0 < -1 or n < (n - 1) that means
//the array does not contain the target value
if (mostRightIndex < mostLeftIndex)
return -1;
//Get the middle position of the array
var middleIndex = (int)(mostLeftIndex + (mostRightIndex - mostLeftIndex) / 2);
//Test if the middle element is the target value (best case scenario)
if (array[middleIndex].CompareTo(target) == 0)
{
return middleIndex;
}
//Is our target to the right or to the left of the current element
return target.CompareTo(array[middleIndex]) < 0 //The target is smaller than the current element, then the target value must be on the left
? RecursiveBinarySearch(array, target, mostLeftIndex, middleIndex - 1) //The target value is bigger than the current element, then the target value must be on the right
: RecursiveBinarySearch(array, target, middleIndex + 1, mostRightIndex);
}
static void Main(string[] args)
{
//An array of clouds...
var sortedArray = new Cloud[]{new Cloud(Cloud.CloudType.Level10), new Cloud(Cloud.CloudType.Level20), new Cloud(Cloud.CloudType.Level30), new Cloud(Cloud.CloudType.Level40), new Cloud(Cloud.CloudType.Level50), new Cloud(Cloud.CloudType.Level60), new Cloud(Cloud.CloudType.Level70), new Cloud(Cloud.CloudType.Level80), new Cloud(Cloud.CloudType.Level90), new Cloud(Cloud.CloudType.Level10), };
//Find the position of the cloud of level 40 in the array-
var position = RecursiveBinarySearch<Cloud>(sortedArray, new Cloud(Cloud.CloudType.Level40));
Console.WriteLine($"There is a Level 40 cloud at position {position}.\n");
}
}