Binary Search

This is the basic divide-and-conquer algorithm, requiring a sorted array. This repeatedly halves the remaining positions to search, until the value is found, or it determines that the value cannot be found. As mentioned, it requires a presorted array, or if unsorted, requires it is sorted. The benefits accrue in instances where the array is sorted once, but searched many times.

On a hypothetical array of 100 items, a linear search has an average performances of O(n/2), or a search of half the positions, 50, to find the item. By comparison, the average performance of Binary Search is O(log n), which for 100 items translates into 4.6, a radically reduced number of iterations, but with greater requirements for logic and memory.

Done in both C#, as an iterative while loop, and F#, as a recursion.

C#

using System;

namespace Algorithms
{
    class BinarySearch
    {
        public BinarySearch()
        {
        }

        public int Search(int num, int[] arrayToSearch)
        {
            int lowPosition = 0;
            int highPosition = arrayToSearch.Length - 1;           
            while (highPosition >= lowPosition)
            {
                //correct calculation for the midpoint
                int position = lowPosition + ((highPosition - lowPosition) / 2);
            
                if (arrayToSearch[position] < num)
                {
                    lowPosition = position + 1;
                }
                else if (arrayToSearch[position] > num)
                {
                    highPosition = position - 1;
                }
                else
                {
                    return position;
                }
            }
            //value not found
            return -1;
        }
    }
}

F#

//a recursive binary search
let rec BinarySearch (arr:array) (num:int) (min:int) (max:int) =    
    if max < min then
        -1 //System.Int32.MinValue
    else
        let position = min + ((max-min)/2)
        if arr.[position] < num then
            // key is in upper subset
            BinarySearch arr num (position+1) max
        else if arr.[position] > num then
            // key is in lower subset
            BinarySearch arr num min (position-1)
        else
            position

//sample sorted array
let baseArray = Array.append [|1..55|] [|99..999|]

//value of max in recursion, used for searches
let maxIndex = ((Array.length baseArray)-1)

//sample searches, including edge cases and returns for value not found
let resultFound1 = BinarySearch baseArray 2 0 maxIndex
let resultFound2 = BinarySearch baseArray 22 0 maxIndex
let resultFound3 = BinarySearch baseArray 222 0 maxIndex
let resultFound4 = BinarySearch baseArray 75 0 maxIndex
let resultFound5 = BinarySearch baseArray 1 0 maxIndex
let resultFound6 = BinarySearch baseArray 0 0 maxIndex
let resultFound7 = BinarySearch baseArray -1 0 maxIndex
let resultFound8 = BinarySearch baseArray 1000 0 maxIndex