03 Jul

C# Sequential Search Example

Sequential search(Linear search) is the simplest search algorithm. It is a special case of brute-force search. It is a method for finding a particular value in a list. To achieve this, it checks every one of its elements one.

Usage:

            //Sorted array
            int[] arr = new int[10]
            {
                1, 2, 4, 11, 20, 28, 48, 84, 96, 106
            };

            int index = SequentialSearch(arr, 20);
            Console.WriteLine("Index of 20 value in array is " + index.ToString());    
            
            //Output:
            //Index of 20 value in array is 4

Sequential Search Implementation:

        private int SequentialSearch(int[] arr, int searchNumber)
        {
            arr[arr.Length - 1] = searchNumber;
            
            int i;
            for (i = 0; arr[i] != searchNumber; i++);
            return (i < arr.Length -1) ? i : -1;
        }

See Also:
Binary Search

03 Jul

C# Binary Search Example

Binary search or half-interval search algorithm finds the position of a specified input value (the search “key”) within an array sorted by key value.
For more information about Binary Search:
http://en.wikipedia.org/wiki/Binary_search_algorithm

This examples shows how to search an item in an array using binary search.

Usage:

            //Sorted array
            int[] arr = new int[10]
            {
                1, 2, 4, 11, 20, 28, 48, 84, 96, 106
            };

            int index1 = arr.ToList().BinarySearch(20);
            int index2 = BinarySearchIterative(arr, 20);
            int index3 = BinarySearchRecursive(arr, 20, 0, arr.Length - 1);
            Console.WriteLine("Index of 20 value in list is " + index1.ToString() + " (using .NET Frameowork)");
            Console.WriteLine("Index of 20 value in list is " + index2.ToString() + " (using BinarySearchIterative method)");
            Console.WriteLine("Index of 20 value in list is " + index3.ToString() + " (using BinarySearchRecursive method)");

            //Output:
            //Index of 20 value in list is 4 (using .NET Frameowork)
            //Index of 20 value in list is 4 (using BinarySearchIterative method)
            //Index of 20 value in list is 4 (using BinarySearchRecursive method)

Iterative and recursive methods:

 
        private int BinarySearchIterative(int[] arr, int searchNumber)
        {
            int left = 0;
            int right = arr.Length - 1;

            int middle;
            while (left <= right)
            {
                middle = (left + right) / 2;
                switch (Compare(arr[middle], searchNumber))
                {
                    case -1: left = middle + 1; break;
                    case 0: return middle;
                    case 1: right = middle - 1; break;
                }
            }
            return -1;
        }

        private int BinarySearchRecursive(int[] arr, int searchnum, int left, int right)
        {
            int middle;
            while (left <= right)
            {
                middle = (left + right) / 2;
                switch (Compare(arr[middle], searchnum))
                {
                    case -1: return BinarySearchRecursive(arr, searchnum, middle + 1, right);
                    case 0: return middle;
                    case 1: return BinarySearchRecursive(arr, searchnum, left, middle - 1);
                }
            }
            return -1;
        }

        private int Compare(int x, int y)
        {
            return x < y ? -1 : (y < x ? 1 : 0);
        }

See Also:
Sequential Search(Linear Search)