This tutorial will show you an algorithm that can search 1,000,000 elements and find it in 20 steps WORST case scenario! This will be in C++. This is part 13 of my programming tutorials; if you want to catch up here are the rest:

Part 1: Hello World!

Part 2: Variables

Part 3: Functions

Part 4: if(), else, else if()

Part 5: Loops

Part 6: Arrays

Part 7: Basic Input/Output

Part 9: Sorting Arrays

Part 10: Random Numbers

Part 11: Colored Text in your Terminal

Part 12: Recursion

The Binary Search

For this algorithm to work, the list of data you are searching must be sorted. This is one of the fastest way to search a list if you know nothing other than that it is sorted. This algorithm first picks the number in the middle of the list. Since we can tell if the number we are looking for is either bigger or smaller than the number in the middle, 50% of the list can already be eliminated! The algorithm simply takes the middle value of the subset that is left, and eliminates 25% more of the data after it compares the number to the value it is searching for. I know that sounded like I pretty much just said the same thing twice... It's because I did! The algorithm is that simple. It keeps doing this until it finds the correct number! Here is a small example to help you better understand:

List: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
...Say we want to find 19.

1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 -- 10 is in the middle, 19 is bigger
2. 11 12 13 14 15 16 17 18 19 20 -- eliminate one side
3. 11 12 13 14 15 16 17 18 19 20 -- 15 is in the middle, 19 is bigger
4. 16 17 18 19 20 -- eliminate one side
5. 16 17 18 19 20 -- 18 is in the middle, 19 is bigger
6. 19 20 -- eliminate one side
7. 19 20 -- 19 is in the middle, this is the correct number

The value was found in only 4 comparisons. This was one of the worse cases (searching for 20 would have been the absolute worst case). Here is how to calculate the worst case scenario for a number of elements:

n = /2^x

Where n is the number of elements, and x is the worst-case number of comparisons.
1,000,000 ≈ 2^20
That means on the worst possible case, it will still only take 20 comparisons to find the number you are looking for in a set of 1,000,000.

Here is a program I wrote to implement this:

#include<iostream>
#include <stdlib.h>
#include <time.h> 
using namespace std;

void bubble_ascending(int arr[], int arrSize)
{
    for(int x = 0; x < arrSize; x++)
    {
        for(int y = 0; y < arrSize-x-1; y++)
        {
            if(arr[y] > arr[y + 1])
            {
                int temp = arr[y];
                arr[y] = arr[y + 1];
                arr[y + 1] = temp;
            }
        }
    }
}

int binaryS(int n, int arrSize, int* arr, int reference)
{
    int mid = arrSize/2;
    if(arrSize % 2 == 1)
        mid++;
    if(arr[mid-1] == n)
    {
        cout << "Found: " << arr[mid-1] << " at index "<< reference << endl << endl;
        return arr[mid-1];
    }
    else if(arrSize == 1)
    {
        cout << n << " not found." << endl << endl;
        return 0;
    }
    cout << arr[mid-1] << endl;
    int newSize;
    int newArr[mid-1];
    
    if(n > arr[mid-1] && mid != 0)
    {
        reference += mid;
        for(int x = mid; x < arrSize; x++)
            newArr[x - mid] = arr[x];
        binaryS(n, mid, newArr, reference);
    }
    if(n < arr[mid-1])
    {
        for(int x = 0; x < mid; x++)
            newArr[x] = arr[x];
        
        binaryS(n, mid, newArr, reference);
    }
}

int main()
{
    int arr[1000];
    srand(time((NULL)));    
    for(int x = 0; x < 1000; x++)
        arr[x] = rand() % 1001;

    bubble_ascending(arr, 1000);

    int arr2[1000000];
    for(int x = 1; x <= 1000000; x++)
        arr2[x] = x;

    binaryS(972, 1000, arr, 0);
    binaryS(1, 1000000, arr2, 0);   

    return 0;
}

Before we look at output, let's break this down. The function "bubble_ascending()" was from my tutorial about sorting. The tutorial explains this function.

main()

• arr is an integer array that holds 1000 random numbers (values 0 - 1000)
  • This is to demonstrate the search with realistic data
• arr gets sorted
• arr2 is an integer array that holds 1,000,000 values in order (1- 1,000,000)
  • This is to demonstrate how the search works mathematically
• Calls binaryS() on arr
  • Searches for 972
• Calls binaryS() on arr2
  • Searches for 1

binaryS()

• This function is recursive -- as it eliminates one side, it sends the other side to itself
• Type int because I can easily exit the function by saying "return 0;"
• n --> number being searched for
• arrSize --> size of the array/subset
• arr --> the array/subset
• reference --> will calculate the index of the number when found
• mid --> index for the middle number (arrSize/2, pretty self explanatory)
• If we have a set with an odd number of values, then add 1 to mid
• "if(arr[mid-1] == n)" --> if the middle number is the number we are searching for, print that it was found and return the value (I haven't implemented a use for returning the value in this program)
• If the size of the array is one, then print a message saying that the value isn't in the set and quit the function
• Print each value we are comparing (for your visual reference!)
• newSize --> the size of the subset that wasn't eliminated
• newArr --> the subset that wasn't eliminated
• If the number being searched for is greater than the mid value:
  • Add the mid value to reference
  • Set the remaining values to newArr
  • call binaryS() again with the new subset and subset size
• If the number being searched for is less than the mid value:
  • Set the remaining values to newArr
  • call binaryS() again with the new subset and subset size

Okay... I know that was a little more detailed than my programs usually are... But I like to write my own instead of stealing programs from websites off of the internet. Let me simplify it little...

Say we have this set: {1,2,3,4,5}
and we search for 4.

• The set is sent to binaryS()
• The mid-point is 3 -- 4 is greater
• binaryS() is called again with the subset {4,5}
  • 4 is the mid-point <-- that is the number!

Here is some output:

[cmw4026@omega test]$ g++ search.cpp
[cmw4026@omega test]$ ./a.out
498
751
878
940
Found: 972 at index 938

499999
249999
124999
62499
31249
15624
7812
3906
1953
976
488
244
122
61
30
15
7
3
Found: 1 at index 0

Another run where 972 wasn't found:

[cmw4026@omega test]$ ./a.out
502
763
887
939
969
989
981
974
970
971
972 not found.

499999
249999
124999
62499
31249
15624
7812
3906
1953
976
488
244
122
61
30
15
7
3
Found: 1 at index 0

Notice that my program found 1 out of 1,000,000 in 19 steps?

I hope this was helpful! If you want more simplified versions of a binary search, just Google it! Mine was a little more detailed, mostly for demonstration purposes. Leave suggestions in the comments!