# SIT221 Data Structures and Algorithms Practical Task 3.2

## Practical Task 3.2

The purpose of this task is to learn implementation of the Binary Search, a classical searching algorithm.

1. Explore the program code attached to this task. Create a new Microsoft Visual Studio project and import the Vector.cs file, or alternatively, extend the project inherited from the previous tasks by copying the missing code from the enclosed template for the Vector<T> className. Import the Tester.cs file to the project to access the prepared Main method important for the purpose of debugging and testing the required algorithmic solution.

2. In this task, you must further extend the Vector<T> classNameto enable searching an element in a sequence of generic data elements. You must add the following functionality to the className:

int BinarySearch( T item )

Searches within the entire sorted Vector<T> for an element using the default comparer and returns the zerobased index of the element, if item is found; otherwise, a negative number (e.g. ‐1). This method uses the default comparer Comparer<T>.Default for type T to determine the order of the elements in the Vector<T>.

int BinarySearch( T item, IComparer<T> comparer )

Searches within the entire sorted Vector<T> for an element using the specified comparer and returns the zerobased index of the element, if item is found; otherwise, a negative number (e.g. ‐1).

Note that you are not allowed to delegate the binary search operation to the Array classNameor any other collection classes. You must implement the Binary Search algorithm from scratch. To learn the similarity with the standard List<T> classNameof .NET Framework, explore the material available at

https://msdn.microsoft.com/en‐us/library/w4e7fxsh(v=vs.110).aspx

and focus on provided remarks and complexity issues.

3. As you progress with the implementation of the algorithm, you should start using the Tester classNamein order to test your implementation of the Binary Search for potential logical issues and runtime errors. This (testing) part of the task is as important as coding. You may wish to extend it with extra test cases to be sure that your solution is checked against other potential mistakes. To enable the tests, remember to uncomment the corresponding code lines. Before you proceed with searching, make sure that your data is sorted according to the dedicated comparer.

### Expected Printout

This section displays the printout produced by the attached Tester className, specifically by its Main method. It is based on our solution. The printout is provided here to help with testing your code for potential logical errors. It demonstrates the correct logic rather than an expected printout in terms of text and alignment.

Test A: Apply BinarySearch searching for number 333 to array of integer numbers sorted in AscendingIntComparer:

Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]

:: SUCCESS

Test B: Apply BinarySearch searching for number 99 to array of integer numbers sorted in AscendingIntComparer:

Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]

:: SUCCESS

Test C: Apply BinarySearch searching for number 996 to array of integer numbers sorted in AscendingIntComparer:

Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]

:: SUCCESS

Test D: Apply BinarySearch searching for number 333 to array of integer numbers sorted in DescendingIntComparer:

Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]

:: SUCCESS

Test E: Apply BinarySearch searching for number 994 to array of integer numbers sorted in DescendingIntComparer:

Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]

:: SUCCESS

Test F: Apply BinarySearch searching for number 101 to array of integer numbers sorted in DescendingIntComparer:

Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]

:: SUCCESS