Exercise 10.10 from Think Julia book

New to Julia
1

hi there,
i can’t understand how to implement a bisection search. I’m trying to do exercise 10.10 from the Think Julia book, here’s the text:
To check whether a word is in the word array, you could use the ∈ operator, but it would be slow because it searches through the words in order.

Because the words are in alphabetical order, we can speed things up with a bisection search (also known as binary search), which is similar to what you do when you look a word up in the dictionary. You start in the middle and check to see whether the word you are looking for comes before the word in the middle of the array. If so, you search the first half of the array the same way. Otherwise you search the second half.

Either way, you cut the remaining search space in half. If the word array has 113,809 words, it will take about 17 steps to find the word or conclude that it’s not there.

Write a function called inbisect that takes a sorted array and a target value and returns true if the word is in the array and false if it’s not.

Is there someone who can explain me how to do it?

1 Like
2

What have you tried so far?

2 Likes
3

I can provide a general description of a function that works.

5

i wrote this code:

function findword(list, k)
    t = []
    for line in eachline(list)
        push!(t, line)
    end
    if k ∈ t
        return true
    else
        return false
    end
end
findword("words.txt", "hola")

it works fine, and it is fast too, but i wasn’t able to implement a bisection search. I was thinking about a recursion but i didn’t find a way to make it work correctly.

1 Like
6

Your function should :

  • find the word that is in the middle of the list.
  • compare it to the wanted word, and conclude :
    • if it is smaller (in the alphabetic sense), then it might be in the first half of the dictionary
    • if it is bigger, it might be in the second half.
    • if it is equal, then definitely you should return true.
  • launch the same computation again, recursively, on the selected half of the list.

Good luck :slight_smile:

2 Likes
7

Your function can begin with two variables representing the sought item’s lowest and highest possible index. These would initially be the extreme values of the indices of the array.

While the lowest possible index is less than or equal to the highest possible index:

  • Make a (roughly) midway guess for the index.

  • If the guess is correct, return the appropriate Bool value.

  • Otherwise, if the guess was too low update the lowest possible index to be one more than the midway guess.

  • Otherwise, update the highest possible index to be one less than the midway guess.

If the lowest possible index exceeds the highest possible index, then that means that the sought item is not in the array and the function returns the appropriate Bool value.

8

Your questions appear to be about algorithms.
You can find some ideas in:
Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet (princeton.edu)
Algorithms - GeeksforGeeks
Data Structure and Algorithms Tutorial (tutorialspoint.com)
among others.

For the fun of it and to see how others are doing:
Julia on Exercism
Codewars - Achieve mastery through coding practice and developer mentorship

The big O notation is to be taken with a grain of salt, as it is an asymptotic value and neglects possibly large factors. See https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472

A small modification of the code there gives:

function findbinsearch(item, collection)
    len = length(collection)
    left = 1
    right = len
    found = false
    while left <= right
        mid = (left + right) >> 1
        if collection[mid] == item
            found = true
            break
        end
        if collection[mid] > item
            right = mid - 1
        else
            left = mid + 1
        end
    end
    found
end

collection = ["tata", "titi", "toto"]

findbinsearch("tati", collection) # -> false
findbinsearch("toto", collection) # -> true
findbinsearch("titi", collection) # -> true
findbinsearch("tata", collection) # -> true
1 Like