# Binary Search Implementation

## Introduction

In a binary search, an ordered list is searched for a key starting with the item at the middle of the list. If the item is not found at the location ,  a determination is made on which half of the list may contain the key, either the upper or lower half. This method is applied to search the midpoint of the half of the list which may contain the key.  This repeats until the key is found, or until the search space is reduced to a single location and  the list can no longer be divided into halves. If the key is found, the location of the element is returned, otherwise a dummy value is returned (e.g -1)

## Binary Search Algorithm

Given a list of items of a finite size and a Key we traverse the list to find the key and output the location of the key found in the list.

Consider the scenario where we have a list, with unique items (in an array) and we wish to find a key:

```Algorithm:
//initialization
//Assume our data is stored in an  array named  list of size N.
list[0..N-1] = {Assume a sorted list}
first=1
last=N-1
result=-1 //used to store the index of a successful search. If result is -1 , the search has failed
middle = (first-last)/2
while (first<=last)
if list[middle]==key then
result= middle
break
else if key<list[middle] then
last=middle;
else
first=middle;
endif
middle=(first-last)/2 + first
endif
endwhile
return result.

```

## Implementation in C code

```/*
Demo: Searching a sorted list using
binary search
*/

#include <stdio.h>
#include <stdlib.h>

int binarySearch(int key, int  list[], int listSize);

int main()
{
int list[10];
list[0]=5;
list[1]=10;
list[2]=15;
list[3]=20;
list[4]=25;
list[5]=30;
list[6]=35;
list[7]=40;
list[8]=45;
list[9]=50;

int key;

printf("\nenter a search key\n");
scanf("%d",&key);
while (key!=-1)
{
int result = binarySearch(key,list,10);
printf("\nSearch result %d\n",result);
printf("\nenter a search key\n");
scanf("%d",&key);
}

return 0;
}

int binarySearch(int key, int  list[], int listSize)
{
/*we use first and last to represent a
portion of the array. Initially, first and last
points to the start of the array and the end of
the array respectively. Middle indexes the location
to the middle of the array.
*/
int result=-1;//-1 represents a failed search
int first=0;
int last=listSize-1;
int middle = (last-first)/2;

while (first<=last)//while first and last have not crossed...
{
if(key==list[middle])//if the key is found....
{
result=middle;
return result;//return the current index and exit function
}
{
if(key<list[middle])//if the key would be found
//from first to middle
last=middle-1;//we now search the lower half
else //key would be found from middle to last
first=middle+1;//we now search the upper half
middle=((last-first)/2)+first;//find the new midpoint.
}
}
return result;
}

```

## Alternate Implementation In C using Recursion

```/*
Demo: Searching a sorted list using
binary search implemented using recursion
*/

#include <stdio.h>
#include <stdlib.h>

int binarySearch(int key, int  list[], int first, int last);

int main()
{
int list[10];
list[0]=5;
list[1]=10;
list[2]=15;
list[3]=20;
list[4]=25;
list[5]=30;
list[6]=35;
list[7]=40;
list[8]=45;
list[9]=50;

int key;

printf("\nenter a search key\n");
scanf("%d",&key);
while (key!=-1)
{
int result = binarySearch(key,list,0,9);
printf("\nSearch result %d\n",result);
printf("\nenter a search key\n");
scanf("%d",&key);
}

return 0;
}

int binarySearch(int key, int  list[], int first, int last)
{
/*we use first and last to represent a
portion of the array. Initially, first and last
points to the start of the array and the end of
the array respectively. Middle indexes the location
to the middle of the array.
*/
int result=-1;//-1 represents a failed search
int middle = (last-first)/2+first;

if (first<=last)//if first and last have not crossed...
{
if(key==list[middle])//if the key is found....
{
result=middle;
return result;//return the current index and exit function
}
{
if(key<list[middle])//if the key would be found
{                   //from first to middle

//we now search the lower half
result= binarySearch(key,list,first,middle-1);
return result;
}

else //key would be found from middle to last
{
result= binarySearch(key,list,middle+1,last);//we now search the upper half
return result;
}

}
}
return result;
}

```

2022/2/3

Added introduction paragraph “In a binary … value is returned (e.g -1)

# Linear search

## Introduction

In a linear search, each element of the array is traversed by using iteration.  Each element in the traversal is compared against a search key. If the key is found, the location of the array index is returned.  If the entire array is traversed without finding the key, dummy value is returned (e.g. -1)

## Linear search Algorithm and Implementation

Given a list of items of a finite size and a Key we traverse the list to find the key and output the location of the key(s) found in the list.

Consider the scenario where we have a list with unique items (in an array) and we wish to find a key.

Demonstration in flowgorithm:

We set up an Real array of size 10  named “list” and initialized with the following values:

We could implement a function as shown below:

Below is an example of how the function can be used:

### Exercises

1. Identify the sentinel variables in the LinearSearch function.

2. Show the trace table for all variables found within linear search when the following function calls are made using the array “list” initialized in the figure 1 above:

a) LinearSearch(10,list,300)
b) LinearSearch(10,list,19)
c) LinearSearch(2,list,19)

Hint:
Use the following trace table format:

• Note that an optional column, called “step” is used to keep track of each variable change such that a step is considered to be any time  time a variable is initialized or changed.
• You do not need to show the list array.
• Assume that no value is assigned during a variable declaration.
E.g

will not be shown as a step in the trace table.

As an example, this table has been filled to the 4th step for part a) above.