Linear search and binary search

Searching (“is this value here, and where?”) is one of the most common things programs do. There are two basic strategies, and which one you can use depends on one question: is the data sorted?

Linear search: check everything

Look at each element in turn until you find the target or run out of elements. It works on any data, sorted or not.

1static int LinearSearch(int[] a, int target)2{3    for (int i = 0; i < a.Length; i++)4        if (a[i] == target) return i;5    return -1;   // not found6}

Best case 1 check, worst case n checks: O(n). For a few hundred items, or a search you do only once, this is perfectly fine and the simplest correct answer.

Binary search: halve the problem

If the array is sorted, you can do far better. Look at the middle element. If it is the target, done. If the target is bigger, it can only be in the right half; if smaller, only in the left half. Throw the other half away and repeat. Like looking up a word in a dictionary: you never read every page.

1static int BinarySearch(int[] a, int target)2{3    int lo = 0, hi = a.Length - 1;          // the range that may still contain target4    while (lo <= hi)5    {6        int mid = lo + (hi - lo) / 2;       // middle of the range7        if (a[mid] == target) return mid;8        if (a[mid] < target) lo = mid + 1;  // discard the left half (and mid)9        else hi = mid - 1;                  // discard the right half (and mid)10    }11    return -1;                              // range is empty: not found12}13 14int[] lengths = { 3, 7, 11, 15, 18, 22, 27, 31 };15Console.WriteLine(BinarySearch(lengths, 22));16Console.WriteLine(BinarySearch(lengths, 20));

5
-1

How fast is it?

Every check halves the remaining range. Starting from n items, after k checks about n / 2ᵏ remain, so at most about log₂ n + 1 checks are needed: O(log n).

Binary search in .NET

Array.BinarySearch and List<T>.BinarySearch are built in. When the value is not found they return a negative number: the bitwise complement (~) of the index where it would be inserted. That is useful for inserting into a sorted list.

1int[] a = { 3, 7, 11, 15 };2 3Console.WriteLine(Array.BinarySearch(a, 11));   // found at index 24 5int r = Array.BinarySearch(a, 8);6Console.WriteLine(r);                           // not found: negative7Console.WriteLine(~r);                          // 8 would go at index 28 9// Keep a List sorted while inserting10var sorted = new List<int> { 3, 7, 11, 15 };11int pos = sorted.BinarySearch(8);12sorted.Insert(pos >= 0 ? pos : ~pos, 8);13Console.WriteLine(string.Join(", ", sorted));

2
-3
2
3, 7, 8, 11, 15

Should I sort first?

Sorting costs O(n log n). For one search, a linear search (O(n)) is cheaper. If you search many times in data that does not change, sort once and every search becomes O(log n). If you only need “is it there?” and never need order, a HashSet<T> is even faster: O(1) per lookup.

1static int SearchInsert(int[] a, int target)2{3    int lo = 0, hi = a.Length - 1;4    while (lo <= hi)5    {6        int mid = lo + (hi - lo) / 2;7        if (a[mid] == target) return mid;8        if (a[mid] < target) lo = mid + 1;9        else hi = mid - 1;10    }11    return lo;   // first index whose value is bigger than target12}13 14int[] a = { 1, 3, 5, 6 };15foreach (int t in new[] { 5, 2, 7, 0 })16    Console.Write(SearchInsert(a, t) + " ");

2 1 4 0