Ask Question

Suppose we are performing a binary search on a sorted array called numbers initialized as follows: / / index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int[] numbers = {-5, - 1, 0, 3, 9, 14, 19, 24, 33, 41, 56, 62, 70, 88, 99}; int index = binarySearch (numbers, 18); Write the indexes of the elements that would be examined by the binary search (the mid values in our algorithm's code).

+3
Answers (1)
  1. 21 January, 23:05
    0
    The indexes of the elements that would be examined by the binary search are

    7 11 9

    numbers[7] = 39

    numbers[11] = 57

    numbers[9] = 42

    The values that would be returned from the search are

    39 57 42

    Explanation:

    The complexity of searching a value in an array using binary search is O (log n). It follows divide and conquer principle. First we have to sort the elements in the array. Here in our case the array is already sorted.

    target = (search for the value) = 42

    numbers[] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    min max

    here assign min = 0 (minimum index)

    max = 14 (maximum index)

    Instead of searching for the target in a sequential manner we are searching by examining the middle term in the array by using the following formula. middle = (min + max) / 2

    step 1) middle = (0 + 14) / 2 = 7 numbers[middle]=numbers[7] = 39

    compare target value with numbers[middle]

    i. e target = 42 > 39, the target value is greater than the numbers[middle]. so we have to move to upper part of the array.

    Then min = middle+1 = 7+1 = 8

    max = (unchanged) 14

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    min max

    step 2) middle = (8 + 14) / 2 = 11 numbers[middle]=numbers[11] = 57

    compare target value with numbers[middle]

    i. e target = 42 < 57, the target value is lesser than the numbers[middle].

    Then min = (unchanged) 8

    max = middle - 1 = 11-1 = 10

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    min max

    step 3) middle = (8+10) / 2 = 9 numbers[middle]=numbers[9] = 42

    i. e target = 42 = 42

    Here stop the process. In this way we found our target using binary search.
Know the Answer?
Not Sure About the Answer?
Find an answer to your question 👍 “Suppose we are performing a binary search on a sorted array called numbers initialized as follows: / / index 0 1 2 3 4 5 6 7 8 9 10 11 12 ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers