Binary Search

// PSC:1.0 BinarySearch
// Description: Finds a target in a sorted list by halving the search range each step

FUNCTION binarySearch(list, n, target)
  LET low = 0
  LET high = n - 1
  WHILE low <= high
    LET mid = (low + high) / 2
    IF list[mid] = target
      RETURN mid
    ELSE IF list[mid] < target
      LET low = mid + 1
    ELSE
      LET high = mid - 1
    END IF
  END WHILE
  RETURN -1
END FUNCTION

BEGIN BinarySearch
  INPUT "How many numbers (sorted, smallest first)? " n
  FOR k FROM 0 TO n - 1
    INPUT "Next number: " value
    LET list[k] = value
  END FOR
  INPUT "Number to find: " target

  LET position = CALL binarySearch(list, n, target)
  IF position = -1
    OUTPUT target " is not in the list"
  ELSE
    OUTPUT target " found at position " position
  END IF
END