2️⃣

# 5.2 Searching

## 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;
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;
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;
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;
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;
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");
}``````

⚖️