L Searching Part A: Binary Search Review.ct p In class we discussed the Binary S

Question

L Searching Part A: Binary Search Review.ct p In class we discussed the Binary Search algorlthm as a better alternative to using a Sequential (Linear) Search 1) Under what drcumstances will the Binary Search algorithm work? 2) When these circumstances a pply, why Binary Search better than Linear Search. 3) Suppose you are given the following list of numbers: 3 8 12 23 29 35 44 49 52 67 89 92 111 122 144 154 If you were using Binary Search to find the number 35 in this list, which numbers in the list would you compare with before finding it? Instructor Initials:

Explanation / Answer

Searching

Part a

1>

Binary search algorithm will work only when the array is a sorted one. This is because binary search algorithm works by dividing the sorted array into two halves and then comparing the value and then deciding on which half of the array to proceed. This process goes on recussively until we come to a result. So if the array is not sorted then this algorithm wont work.

2>

In a sorted list binary search is better than linear search because in linear search each entry needs to be checked and so searching time is more. The worst time complexity in case of linear search is O(n). But in binary search we work by diving the list into two halves successively. So searching time is reduced atleast by half.

3>

Here x (item to be searched) = 35

Length of array(n) = 15

so first we will start from mid position i.e. n/2 = 7.5 = 7(Taking only integer part)

Now the 8th element in the list is 49 which is greater then 35 so we will search for it in the left side of 49.

now n (length of new remaining array) = 6

position = n/2 = 3.

Element at the 3rd position is 23. 23 is greater than 35. So now we will look at the right side of the new remaining array.

now reaming new array is 29 , 35, 44.

so n = 2

position = 2/2 = 1

so will check at index 1.

Here we find a match i.e. element 35. So the search wil end here.

So the numbers compared in the list before finding a match are 49 and 23.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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