Search and Verify Algorithm

When do we use this?

Let’s say you’re keeping track of attendance for an event using an array. Someone comes up to you and asks if their friend “Sahana” is in the attendance roster. Instead of taking the time to search the contents of the array, you can utilize a searching algorithm to verify if Sahana is in the array.

The search and verify algorithm is used to search through the elements of an array and verify whether or not your key, or the item you are searching for, is in the array.

The Algorithm

Setup

First, we setup everything we need to run the algorithm. The first step is to initialize and fill the array we are searching. Then, we enter the key (the item we are searching for).

#include <stdio.h>
    void main()
    {
 
     int a[20];
     int key, size, i;

			//input the size of the array
        scanf("%d", &size);
      //fill the array
        for (i = 0; i < 20; i++) 
        {
            scanf("%d", &a[i]);
        }
			//enter the key (the item you are looking for)
        scanf("%d", &key);
}

The Actual Searching + Verifying

To search the array, we can create a while loop. The conditions of the loop must be from index 0 to the end of the array. In order to make this happen, we need two new variables. One will be low, which will be the starting index of the search, and a high variable, which is the last index of the array.

#include <stdio.h>
    void main()
    {
 
     int a[20];
			//add high and low
     int key, size, i, low, high;

			//input the size of the array
        scanf("%d", &size);
      //fill the array
        for (i = 0; i < 20; i++) 
        {
            scanf("%d", &a[i]);
        }
			//enter the key (the item you are looking for)
        scanf("%d", &key);

			//intialize the while loop, high, and low
			low = 0;
      high = (size - 1);
			while (low <= high){

			}
}

Now, we have to put code inside the while loop. First, we need to use a avg variable to calculate the index we are at after an iteration (the average of low and high). Then, we will check to see if the avg index of the array is = to our key.

#include <stdio.h>
    void main()
    {
 
     int a[20];
			//add high and low
     int key, size, i, low, high;

			//input the size of the array
        scanf("%d", &size);
      //fill the array
        for (i = 0; i < 20; i++) 
        {
            scanf("%d", &a[i]);
        }
			//enter the key (the item you are looking for)
        scanf("%d", &key);

			//intialize the while loop, high, and low
			low = 0;
      high = (size - 1);
			while (low <= high){
			//declare mid
						mid = (low + high) / 2;
			//if this element is equal to our key
            if (key == a[mid]) {
                printf("Yes\n");
                return;
            }
			}
}

Right now we are comparing the same elements over and over again, so that begs the question - How do we iterate? We have to create if statements to account for if a[mid] == key.

#include <stdio.h>
    void main()
    {
 
     int a[20];
			//add high and low
     int key, size, i, low, high;

			//input the size of the array
        scanf("%d", &size);
      //fill the array

				
        for (i = 0; i < 20; i++) 
        {
            scanf("%d", &a[i]);
        }
			//enter the key (the item you are looking for)
        scanf("%d", &key);

			//intialize the while loop, high, and low
			low = 0;
      high = (size - 1);
			while (low <= high){
			//declare mid
						mid = (low + high) / 2;
			//if this element is equal to our key
            if (key == a[mid]) {
                printf("Yes\n");
                return;
            }
			//if key isn't a[mid], change variables accordingly
						if (key < array[mid])
                high = mid - 1;
            else
                low = mid + 1;
			}
			//if key is not in the array
			printf("No\n");
}