Given the following, demonstrate how the Binary Search method of searching an ar

Question

Given the following, demonstrate how the Binary Search method of searching an array will work. At each step, you should list the array slot (index) that is checked, and what this you. Note that you may or may not need all of the passes printed below. Note also that you should not use any optimizations beyond was what covered in the pseudocode for the standard Binary Search. Demonstrate what the algorithm does, when it's asked to find "3" in the following array: Iteration # 1: Index of min element in the current range: _____ Index of Max element: ______ Array index checked: ______ (Value at that index: ______) What does this tell you? Iteration # 2: Index of min element in the current range: _____ Index of Max element: ______ Array index checked: ______ (Value at that index: ______) What does this tell you? Iteration # 3: Index of min element in the current range: _____ Index of Max element: ______ Array index checked: ______ (Value at that index: ______) What does this tell you? Iteration # 4: Index of min element in the current range: _____ Index of Max element: ______ Array index checked: ______ (Value at that index: ______) What does this tell you? Iteration # 5: Index of min element in the current range: _____ Index of Max element: ______ Array index checked: ______ (Value at that index: ______) What does this tell you? Iteration # 6: Index of min element in the current range: _____ Index of Max element: ______ Array index checked: ______ (Value at that index: ______) What does this tell you?_________________

Explanation / Answer

Initially, Array min will be initialized to 0 and Array max will be initialized to 23

Iteration 1

min index is 0
max index is 23

so mid = (max+min)/2 = 11

Array index checked 11
Value at that index is 36

Since the value to be searched i:e 3 is less than 36 that means the value lies on the left side of 36. Thus we change max to mid-1 i:e 11 - 1= 10

Iteration 2

min index is 0
max index is 10

so mid = (max+min)/2 = 5

Array index checked 5
Value at that index is 2

Since the value to be searched i:e 3 is greater than 2 that means the value lies on the right side of 2. Thus we change min to mid+1 i:e 6

Iteration 3

min index is 6
max index is 10

so mid = (max+min)/2 = 8

Array index checked 8
Value at that index is 20

Since the value to be searched i:e 3 is less than 20 that means the value lies on the left side of 20. Thus we change max to mid-1 i:e 8 - 1= 7

Iteration 4

min index is 6
max index is 7

so mid = (max+min)/2 = 6

Array index checked 6
Value at that index is 3

The value 3 has been found and the index 6 will be returned

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.