Skip to content

Exercises · Linear and binary search

Exercises · Chapter 4 · each solution opens with a click · Chapter 4: Linear and binary search · Exercises, volume 1 (PDF)

In the exercises of this chapter the searches are carried out with the two algorithms of the chapter «Linear and binary search», recalled below. The indices of the arrays go from \(1\) to \(n\), and the value \(-1\) is returned when the target value \(m\) is not in the array.

Algorithm: LinearSearch

Input: An array \(a[1..n]\) of \(n\) natural numbers and a target value \(m\)
Output: Index of \(m\) in \(a\), or \(-1\) if not found
1function LinearSearch(a, n, m)
2\(i := 1\)
3while \(i \le n\) do
4if \(a[i] = m\) then
5return \(i\)// Element found at index \(i\)
6end
7\(i \leftarrow i + 1\)
8end
9return \(-1\)// Element not found
10end

Algorithm: BinarySearch

Input: An array \(a[1..n]\) of \(n\) natural numbers sorted in non-decreasing order and a target value \(m\)
Output: Index of \(m\) in \(a\), or \(-1\) if not found
1function BinarySearch(a, n, m)
2\(left\) := \(1\)
3\(right\) := \(n\)
4while \(left \le right\) do
5\(mid\) := \(left + \lfloor (right - left) / 2 \rfloor\)
6if \(a[mid] = m\) then
7return \(mid\)// Element found
8end
9if \(a[mid] < m\) then
10\(left\) \(\leftarrow\) \(mid + 1\)// Search in right half
11end
12else
13\(right\) \(\leftarrow\) \(mid - 1\)// Search in left half
14end
15end
16return \(-1\)// Element not found
17end

Exercise 4.1: Linear and binary search (E1)

Consider the following array:

\[ a = [7, 2, 14, 3, 8, 11, 5, 9] \]

with \(n = 8\).

Questions

  1. Apply the Linear Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 11\)

    2. \(m = 7\)

    3. \(m = 9\)

    4. \(m = 4\)

    5. \(m = 14\)

    For each search, show the execution step by step, indicating at each iteration the values of \(i\), \(a[i]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 11\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 7 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 2 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 14 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 3 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 8 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 11 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 11 is found at index 6.

  2. Search for \(m = 7\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 7 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 7 is found at index 1.

  3. Search for \(m = 9\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 7 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 2 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 14 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 3 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 8 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 11 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 5 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(8\) 8 9 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 9 is found at index 8.

  4. Search for \(m = 4\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 7 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 2 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 14 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 3 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 8 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 11 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 5 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(8\) 8 9 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(-\) 9 \(-\) \(i > n\) \(\Rightarrow\) loop ends, Not found!

    Accordingly, element 4 is not in the array (return \(-1\)).

  5. Search for \(m = 14\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 7 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 2 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 14 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 14 is found at index 3.

Exercise 4.2: Linear and binary search (E2)

Consider the following array:

\[ a = [15, 4, 22, 8, 1, 30, 17] \]

with \(n = 7\).

Questions

  1. Apply the Linear Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 22\)

    2. \(m = 15\)

    3. \(m = 17\)

    4. \(m = 10\)

    5. \(m = 1\)

    For each search, show the execution step by step, indicating at each iteration the values of \(i\), \(a[i]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 22\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 15 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 4 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 22 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 22 is found at index 3.

  2. Search for \(m = 15\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 15 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 15 is found at index 1.

  3. Search for \(m = 17\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 15 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 4 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 22 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 8 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 1 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 30 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 17 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 17 is found at index 7.

  4. Search for \(m = 10\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 15 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 4 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 22 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 8 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 1 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 30 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 17 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(-\) 8 \(-\) \(i > n\) \(\Rightarrow\) loop ends, Not found!

    Accordingly, element 10 is not in the array (return \(-1\)).

  5. Search for \(m = 1\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 15 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 4 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 22 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 8 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 1 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 1 is found at index 5.

Exercise 4.3: Linear and binary search (E3)

Consider the following array:

\[ a = [6, 19, 3, 27, 12, 5, 33] \]

with \(n = 7\).

Questions

  1. Apply the Linear Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 27\)

    2. \(m = 6\)

    3. \(m = 33\)

    4. \(m = 15\)

    5. \(m = 3\)

    For each search, show the execution step by step, indicating at each iteration the values of \(i\), \(a[i]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 27\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 6 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 19 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 27 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 27 is found at index 4.

  2. Search for \(m = 6\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 6 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 6 is found at index 1.

  3. Search for \(m = 33\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 6 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 19 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 27 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 12 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 5 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 33 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 33 is found at index 7.

  4. Search for \(m = 15\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 6 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 19 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 27 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 12 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 5 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 33 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(-\) 8 \(-\) \(i > n\) \(\Rightarrow\) loop ends, Not found!

    Accordingly, element 15 is not in the array (return \(-1\)).

  5. Search for \(m = 3\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 6 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 19 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 3 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 3 is found at index 3.

Exercise 4.4: Linear and binary search (E4)

Consider the following array:

\[ a = [50, 25, 75, 10, 40, 60, 5] \]

with \(n = 7\).

Questions

  1. Apply the Linear Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 10\)

    2. \(m = 50\)

    3. \(m = 5\)

    4. \(m = 30\)

    5. \(m = 75\)

    For each search, show the execution step by step, indicating at each iteration the values of \(i\), \(a[i]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 10\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 50 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 25 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 75 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 10 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 10 is found at index 4.

  2. Search for \(m = 50\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 50 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 50 is found at index 1.

  3. Search for \(m = 5\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 50 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 25 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 75 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 10 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 40 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 60 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 5 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 5 is found at index 7.

  4. Search for \(m = 30\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 50 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 25 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 75 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 10 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 40 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 60 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 5 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(-\) 8 \(-\) \(i > n\) \(\Rightarrow\) loop ends, Not found!

    Accordingly, element 30 is not in the array (return \(-1\)).

  5. Search for \(m = 75\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 50 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 25 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 75 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 75 is found at index 3.

Exercise 4.5: Linear and binary search (E5)

Consider the following array:

\[ a = [11, 7, 3, 18, 24, 9, 16, 2] \]

with \(n = 8\).

Questions

  1. Apply the Linear Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 24\)

    2. \(m = 11\)

    3. \(m = 2\)

    4. \(m = 8\)

    5. \(m = 3\)

    For each search, show the execution step by step, indicating at each iteration the values of \(i\), \(a[i]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 24\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 11 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 7 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 18 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 24 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 24 is found at index 5.

  2. Search for \(m = 11\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 11 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 11 is found at index 1.

  3. Search for \(m = 2\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 11 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 7 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 18 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 24 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 9 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 16 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(8\) 8 2 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 2 is found at index 8.

  4. Search for \(m = 8\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 11 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 7 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(4\) 4 18 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(5\) 5 24 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(6\) 6 9 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(7\) 7 16 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(8\) 8 2 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(-\) 9 \(-\) \(i > n\) \(\Rightarrow\) loop ends, Not found!

    Accordingly, element 8 is not in the array (return \(-1\)).

  5. Search for \(m = 3\):

    iteration \(i\) \(a[i]\) action
    \(1\) 1 11 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(2\) 2 7 \(a[i] \neq m\) \(\Rightarrow\) continue
    \(3\) 3 3 \(a[i] = m\) \(\Rightarrow\) Found!

    Accordingly, element 3 is found at index 3.

Exercise 4.6: Linear and binary search (E6)

Consider the following array, sorted in non-decreasing order:

\[ a = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78, 89] \]

with \(n = 12\).

Questions

  1. Apply the Binary Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 23\)

    2. \(m = 2\)

    3. \(m = 89\)

    4. \(m = 50\)

    5. \(m = 1\)

    For each search, show the execution step by step, indicating at each iteration the values of \(left\), \(right\), \(mid\), \(a[mid]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 23\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 12 6 23 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 23 is found at index 6.

  2. Search for \(m = 2\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 12 6 23 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 5\)
    \(2\) 1 5 3 8 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(3\) 1 2 1 2 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 2 is found at index 1.

  3. Search for \(m = 89\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 12 6 23 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(2\) 7 12 9 56 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 10\)
    \(3\) 10 12 11 78 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 12\)
    \(4\) 12 12 12 89 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 89 is found at index 12.

  4. Search for \(m = 50\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 12 6 23 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(2\) 7 12 9 56 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 8\)
    \(3\) 7 8 7 38 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 8\)
    \(4\) 8 8 8 45 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 9\)
    \(-\) 9 8 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 50 is not in the array (return \(-1\)).

  5. Search for \(m = 1\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 12 6 23 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 5\)
    \(2\) 1 5 3 8 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(3\) 1 2 1 2 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 0\)
    \(-\) 1 0 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 1 is not in the array (return \(-1\)).

Exercise 4.7: Linear and binary search (E7)

Consider the following array, sorted in non-decreasing order:

\[ a = [1, 3, 5, 7, 9, 11, 13, 15] \]

with \(n = 8\).

Questions

  1. Apply the Binary Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 7\)

    2. \(m = 1\)

    3. \(m = 15\)

    4. \(m = 10\)

    5. \(m = 20\)

    For each search, show the execution step by step, indicating at each iteration the values of \(left\), \(right\), \(mid\), \(a[mid]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 7\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 8 4 7 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 7 is found at index 4.

  2. Search for \(m = 1\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 8 4 7 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 3\)
    \(2\) 1 3 2 3 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 1\)
    \(3\) 1 1 1 1 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 1 is found at index 1.

  3. Search for \(m = 15\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 8 4 7 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 5\)
    \(2\) 5 8 6 11 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(3\) 7 8 7 13 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 8\)
    \(4\) 8 8 8 15 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 15 is found at index 8.

  4. Search for \(m = 10\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 8 4 7 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 5\)
    \(2\) 5 8 6 11 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 5\)
    \(3\) 5 5 5 9 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(-\) 6 5 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 10 is not in the array (return \(-1\)).

  5. Search for \(m = 20\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 8 4 7 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 5\)
    \(2\) 5 8 6 11 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(3\) 7 8 7 13 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 8\)
    \(4\) 8 8 8 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 9\)
    \(-\) 9 8 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 20 is not in the array (return \(-1\)).

Exercise 4.8: Linear and binary search (E8)

Consider the following array, sorted in non-decreasing order:

\[ a = [10, 20, 30, 40, 50, 60] \]

with \(n = 6\).

Questions

  1. Apply the Binary Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 40\)

    2. \(m = 10\)

    3. \(m = 60\)

    4. \(m = 25\)

    5. \(m = 70\)

    For each search, show the execution step by step, indicating at each iteration the values of \(left\), \(right\), \(mid\), \(a[mid]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 40\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 30 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 50 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 4\)
    \(3\) 4 4 4 40 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 40 is found at index 4.

  2. Search for \(m = 10\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 30 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(2\) 1 2 1 10 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 10 is found at index 1.

  3. Search for \(m = 60\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 30 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 50 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(3\) 6 6 6 60 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 60 is found at index 6.

  4. Search for \(m = 25\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 30 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(2\) 1 2 1 10 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 2\)
    \(3\) 2 2 2 20 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 3\)
    \(-\) 3 2 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 25 is not in the array (return \(-1\)).

  5. Search for \(m = 70\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 30 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 50 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(3\) 6 6 6 60 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(-\) 7 6 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 70 is not in the array (return \(-1\)).

Exercise 4.9: Linear and binary search (E9)

Consider the following array, sorted in non-decreasing order:

\[ a = [4, 8, 15, 16, 23, 42] \]

with \(n = 6\).

Questions

  1. Apply the Binary Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 15\)

    2. \(m = 4\)

    3. \(m = 42\)

    4. \(m = 20\)

    5. \(m = 2\)

    For each search, show the execution step by step, indicating at each iteration the values of \(left\), \(right\), \(mid\), \(a[mid]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 15\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 15 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 15 is found at index 3.

  2. Search for \(m = 4\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 15 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(2\) 1 2 1 4 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 4 is found at index 1.

  3. Search for \(m = 42\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 23 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(3\) 6 6 6 42 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 42 is found at index 6.

  4. Search for \(m = 20\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 23 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 4\)
    \(3\) 4 4 4 16 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 5\)
    \(-\) 5 4 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 20 is not in the array (return \(-1\)).

  5. Search for \(m = 2\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 6 3 15 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(2\) 1 2 1 4 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 0\)
    \(-\) 1 0 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 2 is not in the array (return \(-1\)).

Exercise 4.10: Linear and binary search (E10)

Consider the following array, sorted in non-decreasing order:

\[ a = [3, 6, 9, 12, 15, 18, 21, 24, 27, 30] \]

with \(n = 10\).

Questions

  1. Apply the Binary Search algorithm to the array \(a\) for each of the following target values:

    1. \(m = 18\)

    2. \(m = 3\)

    3. \(m = 30\)

    4. \(m = 10\)

    5. \(m = 35\)

    For each search, show the execution step by step, indicating at each iteration the values of \(left\), \(right\), \(mid\), \(a[mid]\) and the result of the comparison, and give the value returned by the algorithm.

Solution

  1. Search for \(m = 18\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 10 5 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(2\) 6 10 8 24 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 7\)
    \(3\) 6 7 6 18 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 18 is found at index 6.

  2. Search for \(m = 3\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 10 5 15 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 4\)
    \(2\) 1 4 2 6 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 1\)
    \(3\) 1 1 1 3 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 3 is found at index 1.

  3. Search for \(m = 30\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 10 5 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(2\) 6 10 8 24 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 9\)
    \(3\) 9 10 9 27 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 10\)
    \(4\) 10 10 10 30 \(a[mid] = m\) \(\Rightarrow\) Found!

    Accordingly, element 30 is found at index 10.

  4. Search for \(m = 10\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 10 5 15 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 4\)
    \(2\) 1 4 2 6 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 3\)
    \(3\) 3 4 3 9 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(4\) 4 4 4 12 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 3\)
    \(-\) 4 3 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 10 is not in the array (return \(-1\)).

  5. Search for \(m = 35\):

    iteration \(left\) \(right\) \(mid\) \(a[mid]\) action
    \(1\) 1 10 5 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(2\) 6 10 8 24 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 9\)
    \(3\) 9 10 9 27 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 10\)
    \(4\) 10 10 10 30 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 11\)
    \(-\) 11 10 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Not found!

    Accordingly, element 35 is not in the array (return \(-1\)).