Array Searching with Binary Search

Searching Arrays

  • Final array method: searching arrays.
  • Checking if an array contains an element or not.
  • Binary search method: A classical search algorithm in computer science.
  • Requires a sorted array (builds upon the sorting concepts).
  • Using strings rather than integers in this example.

Case Study: Marie's Bakery

  • Marie loves cakes and received excellent service.
  • Wants to tip the employee but only remembers the name might be Sam or Simon.
  • Goal: Search the employee names to see if Sam or Simon work at the bakery.

Steps to Determine if Sam or Simon are Employees

  1. Initialize an array of names.
  2. Sort the names array.
  3. Perform a binary search for Sam and Simon.
  4. Report if Simon or Sam are employees.

Implementation Details

Step 1: Initialize the Array
  • Create a new array containing the names.
  • Use a For Each loop to print the names to the console for verification.
Step 2: Sort the Array
  • Sorting code similar to the previous examples.
  • Print the names after sorting to verify correct order.
  • Demonstrates that the sort method works with strings as well as integers.
Step 3: Binary Search
  • Syntax: array.BinarySearch(array_to_search, element_to_search)
  • Return value: An integer.
    • Positive or zero: Element found; the number is the index.
    • Negative: Element not found.
Example
  • Assume the names array is sorted.
  • Search for "Simon".
    • If the result is ≥0\ge 0, print "Simon is an employee."
    • If the result is < 0, print "Simon is not an employee."
  • Repeat the experiment for "Sam". The result is that Sam is not an employee.

Test Cases

  • Absence Test Case: Empty array.
    • Should report that the person is not an employee, regardless of the name.
  • Boundary Tests: Array with one element.
    • Search for a person who is an employee.
    • Search for a person who is not an employee.
  • Another Boundary Test: Look at the first element of the sorted array (e.g., "Felipe").
  • Tests on an array with multiple elements.
  • Extend test cases to include all uppercase and all lowercase string values.

Improvements

  • Add an if test for a zero-length array to report this explicitly.
  • Place the names to be searched (Simon and Sam) inside another array.
  • Place the search within a for loop.
  • Make character case insensitive (e.g., uppercase "Simon" treated the same as any other capitalization).

Summary of Array Methods

  • Covered array methods: copy, sort, reverse, and binary search.
  • These methods are commonly used in more complex problems.
  • Search for other array methods in textbooks, online, or in Microsoft documentation.