# Exercises

# 15.3. Exercises#

Many of these exercises are taken from past exams of APS105 Computer Fundamentals courses at University of Toronto. The solutions are provided in the answer boxes.

Headings in this page classify the exercises into different categories: **[Easy]**, **[Intermediate]**, and **[Challenging]**. I suggest you start by easy exercises and work your way up to the challenging ones.

**Question 5 in Winter 2018 [Easy]**

Complete the following C program by inserting the condition of the while loop in the function `search`

. The function is designed to search for an int-type item, called `key`

, in a linked list, pointed to by head.

```
typedef struct node {
int data;
struct node *link;
} Node;
Node *search(Node *head, int key) {
Node *current = head;
// insert your code in the line below between the parentheses
while ( ) {
current = current->link;
}
return current;
}
```

Answer

```
typedef struct node {
int data;
struct node *link;
} Node;
Node *search(Node *head, int key) {
Node *current = head;
// insert your code in the line below between the parentheses
while (current != NULL && current->data != key) {
current = current->link;
}
return current;
}
```

**Question 1.7 in Fall 2011 [Easy]**

Your task is to complete the function below so that it contains a non-recursive implementation of the binary search algorithm. The parameter `values`

is an array of `int`

type variables. The items in the values array have been sorted into descending (non-ascending) order. Parameter `n`

is the number of elements in the `values`

array. Parameter `item`

is the item being searched for in the values array.

The function should return -1 if `item`

is not found in the array. Otherwise, the function should return the index position within the array at which `item`

is found.

**Important:** your function should assume that `values`

is a sorted array in descending (non-ascending) order.

**Important:** Your solution must **not** use recursion.

```
int binSearch(int values[], int n, int item) {
int left = 0;
int right = n - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (item == values[middle]) return middle;
// WRITE YOUR CODE HERE:
}
}
```

Answer

```
int binSearch(int values[], int n, int item) {
int left = 0;
int right = n - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (item == values[middle]) return middle;
// SOLUTION:
if (item < values[middle])
left = middle + 1;
else
right = middle - 1;
}
}
```