Today I got back into reading Sedgewick's Algorithms book, in which I have been translating the examples into C#, VB and C++/CLI to help me really wrap my head around the sample implementations. I am sure most of you are aware of how to implement a Sequential search and a Binary search, but I thought I would post the C# sample code for the heck of it.
For those of you not coming from a CompSci background (such as myself), you probably have written these algorithms or at least seen them but may not have know their identities ...
NOTE: these are searching an ordered array
1 using System;
2 using System.Collections.Generic;
3 using System.Text;
4
5 namespace SequentialAndBinarySearchs
6 {
7 class Program
8 {
9 static void Main(string[] args)
10 {
11 int[] numbers = new int[] { 1488, 1578, 1973, 3665, 4426,
12 4548, 5435, 5446, 6333, 6385, 6455, 6504, 6937, 6965,
13 7104, 7230, 8340, 8958, 9208, 9364, 9550, 9645, 9686};
14
15 Console.WriteLine(SequentialSearch(numbers, 5435));
16
17 Console.WriteLine(BinarySearch(numbers, 5435));
18 }
19
20 // Sequential Search
21 // In an ordered table examines N numbers for each search in the worst case
22 // and about N/2 numbers for each search on average
23 static int SequentialSearch(int[] a, int v)
24 {
25 int count = 0;
26 for (int i = 0; i <= a.Length; i++)
27 {
28 Console.WriteLine("Checking ... {0}", ++count);
29 if (v == a[i])
30 return i;
31
32 }
33
34 return -1;
35 }
36
37 // Binary Search
38 // Never examines more than (log N) + 1 numbers
39 static int BinarySearch(int[] a, int v)
40 {
41 int l = 0;
42 int r = a.Length;
43 int count = 0;
44
45 while (r >= l)
46 {
47 Console.WriteLine("Checking ... {0}", ++count);
48
49 int m = (l + r) / 2;
50 if (v == a[m])
51 return m;
52
53 if (v < a[m])
54 r = m - 1;
55 else
56 l = m + 1;
57 }
58
59 return -1;
60 }
61 }
62 }