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

F#

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

## Comments

## Post a Comment