HSC SDD - Planning and designing software solutions

A binary search is used on a sorted array to find a required element more quickly than using a linear search. It divides the data set into two parts and determines in which part the element is to be found. That part of the array is again divided into two parts and a further decision is made as to which part may contain the target value. The process is continued until either the value is found or there are no more elements in the data set to be checked. If a match is found, the position of the match is reported, otherwise a message is written telling the user that the target is not present in the data. At each division there are three possibilities for the target (if it exists in the array):

1. the target lies at the division point;
2. the target lies to the left of the division point 3.the target lies to the right of the division point

Head to http://algorithms.openmymind.net/search/binarysearch.html and watch how the binary search moves through the data.

Pseudocode example:

BEGIN BinarySearch
  Let Lower = 1
  Let Upper = number of elements in the array
  Let FoundIt = false
  Get RequiredName
  REPEAT
    Let Middle = (Upper + Lower) / 2
    Let Middle = integer part of Middle
    IF RequiredName = Name (Middle) THEN
      Let FoundIt = true
      Let PositionFound = Middle
    ELSE
      IF RequiredName < Name (Middle) THEN
        Let Upper = Middle – 1
      ELSE
        Let Lower = Middle + 1
      ENDIF
    ENDIF
  UNTIL FoundIt OR Lower > Upper
  IF FoundIt THEN
    Display “Required name found at ” PositionFound
  ELSE
    Display “Required name ” RequiredName “ not found.”
  ENDIF
END BinarySearch

ACTIVITY 3

Using the C# code from Linear Search as a base, create a Binary Search.

Submit your code and .exe here: