Binary Search WEEK 5 LESSON 1

Describe the steps involved in a binary search to find the value 47 in the list below.

4, 7, 8, 21, 46, 47, 51

Find the midpoint of the data which is element three value 21.

if (21) is equal to our search item (47) search item is found false in this case.

If search item is greater than the midpoint of 21 search second half of the list.

If midpoint 47 is equal to 47 search item is found true and search

Binary Search code

array myIntegers[5] = [12,16,19,22,25]

start = 0 (start index)

end = 4 (end index)

found = false (searchItem has been found yet)

input searchItem(‘Please enter search item‘)

midPoint = 0

while (found == false AND start <= end)

midPoint = (start + end) DIV 2  

if (myIntegers[midPoint] == searchItem) then

found = true

elseif (myIntegers[midPoint] > searchItem)

end = midPoint - 1

else 

start = midPoint +1

endif

endwhile

 

if (found == true) then

print(“Item found at “ + midPoint)

endif

Can a binary search use strings?

Yes because we can convert the characters to its representative ASCII value

How must the data set be arranged for the binary search to work?

It must be a sorted list

Why would we use a binary search rather than a linear search?

For larger sets of data

Is a binary search always faster than a linear search?

Not always if the searchItem is at the start the linear search will have fewer passes

What are the similarities and differences between linear and binary search?

Linear search and Binary search through a array or list for specific item

Binary Search is more efficient for larger datasets

Binary search has to be sorted list