Search and Verify AlgorithmWhen do we use this?The AlgorithmSetupThe Actual Searching + VerifyingMini Project
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"); }
Mini Project
You are given an array of ages (make sure to allow the user to input the ages), and check if user inputted age they are looking for is in this array!
Solution Code
#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"); }
Copyright © 2021 Code 4 Tomorrow. All rights reserved.
The code in this course is licensed under the MIT License.
If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.