Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-05-01

posted May 1, 2019, 6:26 AM by Konstantinovich Samuel   [ updated May 1, 2019, 6:48 AM ]
Binary Search - Discussion

Do now:
1-Write an algorithm: (Write out steps) To find the 1st location of a specified word in a book: e.g.  Find the word "green" in Dante's Inferno.
2-Write an algorithm: (Write out steps) To find a specified word in a dictionary. (The main word being defined, not as part of a definition)
3-Write out:  Why would your methodology be different?


Binary Search
Binary Search precondition: The data set must be sorted.
 0  1   2   3   4   5   6   7   8    9   10   11   12   13
[5, 9, 11, 55, 67, 84, 91, 98, 99, 101, 109, 123, 144, 150]



data = SORTED_ARRAY
size = data.length
target = VALUE_TO_FIND
lo = 0
hi = size - 1
while target not found:
    if ??1??:
        return -1;            //target not found

    index = ??2??;            //where do you look?
    if data[index] == target:
        return index;         //found the target

    if data[index] < target:  //location is too small
        ??3??

    if data[index] > target:  //location too big
        ??4??







Processing - A tool that you should play with if you want to use it on your final project.
Comments