binary search

Binary Search

Linear Search
Array(11,23,8, etc etc)
Linear time

Big idea: divide and conquer, reduce search area by half each time
but only if array is sorted

Pseudocode
Repeat following steps until sub array is of size 0
Calculate midpoint of current array

If target at middle, stop
Else if target < middle, repeat but change endpoint to be just left of middle
Else if target > middle, repeat but change start point to be just right of middle

==========

Example:

Array(11, 23, 8, 14, 30, 9, 6, 17, 22, 28, 25, 15, 7, 10, 19)
Sort it
Array(6,7,8,9,10,11,14,15,17,19,22,23,25,28,30)

Target = 19
Start = 0
End = 14
Middle = 7 ((end + start)/2)

Is 15 (index 7) what we are looking for? No.  Target > 15 so we move right; the new start point is 8
8 + 14 = 22/2 = 11 (new middle)

Is 23 (index 11) what we want? No.  Target < 23 so we move left; new end point is 10
New middle is 9
Is 19 what we want? Yes!

===========

If we don't find the element (because it's not in the array) then the start and end will be the same and that one element will still not be the right one