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 11: Colored Text in your Terminal
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.
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:
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
#include
#include
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.
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.
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!