101companies

Headline

Solve the search problem for sorted input

Description

Semi-formally, binary search can be described by an algorithm as follows:

  • Given is a sorted list l and a value v of the element type of l.
  • If l is the empty list then return False.
  • Let m be the element in the "middle" of l.
  • If m equals v, then return True.
  • If m < v, then recursively search v in the list containing all elements to the right of m.
  • If m > v, then recursively search v in the list containing all elements to the left of m.
Please note that this formulation also expresses that the element type must admit comparison for comparison.

Illustration

Binary search

-- Polymorphic binary search
-- Assume that input list is sorted
search :: Ord a => [a] -> a -> Bool
search [] _ = False
search xs x =
   if x < y then search ys1 x
   else if x > y then search ys2 x
   else True
  where
    ys1 = take l xs
    (y:ys2) = drop l xs
    l = length xs `div` 2

The implemented search function can be applied as follows: 

-- Illustrate binary search
main = do
  let input = [1,2,3,4,4]
  print $ search input 1 -- True
  print $ search input 5 -- False

Note that the input list is readily sorted. The less efficient, linear search does not require the input list to be sorted.

We may also represent the input as a sorted tree. In this manner, the decision of going to the left or the right side after "halving" is much more straightforward. Here is a suitable algebraic data type for trees: 

-- Binary trees
data Tree a = Empty | Fork a (Tree a) (Tree a)

The corresponding search function looks like this: 

-- Polymorphic binary search
-- Assume that input tree is sorted
search :: Ord a => Tree a -> a -> Bool
search Empty _ = False
search (Fork x1 l r) x2 =
  if x2 < x1
    then search l x2
    else if x2 > x1
      then search r x2
      else True

A demo follows: 

-- Illustrate binary search
main = do
  let input = Fork 3 (Fork 1 Empty Empty) (Fork 42 Empty Empty)
  print $ search input 1 -- True
  print $ search input 3 -- True
  print $ search input 42 -- True
  print $ search input 88 -- False

Citation

(http://en.wikipedia.org/wiki/Binary_search_algorithm, 21 April 2013)

In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array. ... In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned.

(C) 2012-2024 softlang.org and contributors

There are no revisions for this page.

User contributions

    This user never has never made submissions.

    User edits

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.