Skip to main content

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

Comments

Popular posts from this blog

Heap Sort

Heap Sort is interesting because the use of the 'heapify' method that creates a binary tree as a flat array. First, a binary tree, also known as a heap, is created, and then the same function is used to sort the elements. In a heap, the first node in the array at zero (0) is the top node of the binary tree. The next two (2) items are the two (2) subnodes of the top node, and so on. For each node at a position (positionIndex), its 2 subnodes are in the following positions:

int left = 2 * positionIndex + 1;int right = 2 *  positionIndex + 2;
The CommonMethods.Swap() function is a reusable class, since swapping values by position is a common action during these example sorts.

Class

using System;

namespace Algorithms
{
    class HeapSort
    {
        public int[]  Sort()
        {
            //creates array
            int[] arrayToSort = { 11, 1, 22, 2, 33, 3, 44, 4, 55, 5, 66, 6, 7, 77, 88 };

            //creates a heap
            BuildHeap(arrayToSort);

            //sorts a heap
         …

Bucket Sort

This following uses the divide-and-conquer method of resolution, by dividing the problem into smaller arrays, sorting each smaller array, then reinserting the subarrays back into the original array.  This is not a pure solution, in that it uses the .NET List, rather than a linked list struct.

using System;
using System.Collections;
using System.Collections.Generic;

namespace Algorithms
{
    class BucketSort
    {
        public int[] Sort()
        {   
            //creates arbitrary array
            int[] arrayToSort = { 11, 7, 22, 2, 33, 3, 17, 44, 4, 55, 5, 66, 6, 1, 77 };
            //create bucket using hash, x/10
            List<int>[] bucketList = CreateHashedArray(arrayToSort, 10);
            //sort the bucket list back into the original array
            ReorderList(bucketList, arrayToSort);
            return arrayToSort;
        }

        private int hashFunction(int num, int buckets)
        {
            return num / buckets;
        }

        private List<int>[] CreateHashed…