Programming Concepts: Binary search

From Wikibooks, open books for an open world
Jump to navigation Jump to search

UNIT 3 - ⇑ Programming Concepts ⇑

← Tree traversal algorithms for a binary tree Binary search Insertion sort →


Binary Search
ClassSearch algorithm
Data structureArray
Worst case performanceO(log n)
Best case performanceO(1)
Average case performanceO(log n)
Worst case space complexityO(1)

Binary search locates the position of an item in a sorted array.

A quick way to remember how this search works is to imagine searching for words beginning with 'S' in a dictionary. You know that the dictionary is in alphabetical order but you don't yet know if there are any words beginning with 'S' in it, nor do you know where the 'S' section begins and ends.

Description Traced Alphabet

Open the Dictionary in the centre - you find the letter 'L'
Letters before 'L' aren't any good, so ignore that part of the dictionary
Taking the 'L' to 'Z' section, you split it in half and find 'P'
Letters before 'P' aren't any good, so ignore that part of the dictionary
Taking the 'P' to 'Z' section, you split it in half and find 'U'
Letters after 'U' aren't any good, so ignore that part of the dictionary
Taking the 'P' to 'U' section, you split it in half and find 'S'

abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

how efficient is it? how many searches for x number of items? what is the equation? give an example. Why is it better than a linear search. Can you use it on ordered lists or unordered lists?

How to work out the maximum number of searches (n) on a x sized array:

2^n > size of list (x) where n = max searches

For example, if we had a 3 item array

2^2 = 4 > 3 therefore max searches = 2
 min := 1;
 max := N; {array size: var A : array [1..N] of integer}
 repeat
  mid := (min+max) div 2;
  if x > A[mid] then
   min := mid + 1;
  else
   max := mid - 1;
 until (A[mid] = x) or (min > max);

Note: This code assumes 1-based array indexing. For languages that use 0-based indexing (most modern languages), min and max should be initialized to 0 and N-1.

Note 2: The code above does not return a result, nor indicates whether the element was found or not.

Note 3: The code above will not work correctly for empty arrays, because it attempts to access an element before checking to see if min > max.

Exercise: Linear Search
Given a 256 item sorted list, what is the maximum number of searches needed to find an item?

Answer:

9 as:
2^n > size of list where n = max searches 2^9 = 512 > 256
Given a 1000 item sorted list, what is the maximum number of searches needed to find an item?

Answer:

10 as: 
2^n > size of list where n = max searches
2^10 = 1024 > 1000