|
Introduction
Techniques for searching arrays are normally taught during entry level programming classes after the student has had an introduction to language syntax, data types, and control structures (especially looping). While studying these techniques, students learn logical thinking skills and sharpen their sense of creativity. There will be times when a programmer will need to search an entire array to look for specific data, whether it be integer values, floating point values, or character values. Problems requiring insertion into an array, deletion from an array, finding maximum and minimum values, and simply determining if a value is present require some method of searching. In this article, I introduce two standard methods for searching arrays: a linear search, and a binary search. I will first present a simple problem to be solved by searching, and then show examples of each search method using the C++ and ADA programming languages.
"Searching" Mindset
Developing a search algorithm for an array basically requires a programmer to have knowledge of two skills: good sense of program logic and "loop" syntax. An array is a bounded structure, which implies that it has a minimum storage location and a maximum storage location. Searching for an array element, normally called a "target", will require the algorithm to start from either the minimum or maximum location and traverse to either the maximum or minimum location in pursuit of the "target". The size of the array should be known by the programmer. In most cases, it is best to declare the array size as a global constant. Because of this type of traversing action with known beginning and ending locations as well as array size, a loop will be used as the search method. The logic is fairly simple to comprehend once presented with the code. The programmer should attempt to mimic the "mind" of a computer when developing the search algorithm. This can be done by monitoring all variable values using pen and paper during each loop cycle. By logically performing the search using his "mind" prior to any program compilations, the programmer will fully understand the algorithm.
The Problem [Jump to Example Program]
Consider the situation where you have an array of integer values. These values represent the product identification numbers for the stock of a particular department within a store. Your boss needs you to write code that will determine if a particular product is in stock by using the id number. This code will be embedded into a system used by sales clerks. When a customer wants to know if a product that is not on display in the store is in stock, this code will be used to determine if the product is available in stock.
Search Algorithms
You decide to write the function using the following two standard methods: linear search and binary search. You will then decide which method is the most efficient for your needs. We will begin by examining a linear search routine.
Linear Search
When an object is said to linear, it implies that it is of, or relating to a line. From a programmer's perspective, a linear search will sequentially evaluate each element in the array to see if it matches the target value, which is the element you are searching for. You can think of the array as a line connected by many dots. The "dots" can be though of as array rows. The linear search will compare each dot (row) in the line with the "target". Linear searches normally begin by examining the value of array position one. When using the algorithm covered in this article, if this value matches the "target", a value of 0 will be returned; otherwise, the search will move to array position 1 and repeat the process (return a value of 1 if the target is equal to the value in position 1; if not, move on to array position 2). Repeat this process until the target is found (return the array position where it was found) or the end of the array is reached without finding the target. If the target is not found, the function will simply return a value of -1 to indicate a failure.
The following is a C++ function definition that can be used as a linear search to handle our previous stock identification problem. The variable size represents the size of the array. For example, if size equals a value of 100, then the array will store values in positions 0 through 99.
int linearSearch(int arr[], int size, int target)
{
int position = 0, result = -1;
bool isFound = 0;
while ( !isFound && position < size )
{
if (arr[position] == target)
{
result = position; // target position
isFound = 1; // to break loop
}
position++;
}
return result;
}
|
When the above C++ function is called, one of two values will be returned: the target's position in the array or a value of -1 indicating failure. The following is the same algorithm written using the ADA programming language.
function linearSearch(arr : tMyArr; target : integer; size : integer) return integer is
result : integer := -1;
position : integer := 0;
isFound : boolean := FALSE;
begin
while not isFound and position < size loop
if arr(position) = target then
result := position;
isFound := TRUE;
end if;
position := position + 1;
end loop;
return result;
end linearSearch;
|
You completed the implementation of the linear search and would like to implement a binary search to figure out which method is most efficient for the product identification problem. Let's attack the binary search now.
Binary Search
It is important to note that a requirement for a binary search is for the array to be previously sorted into ascending or descending order. Binary implies that an object consists of two components or parts. When performing binary array searches, the array being searched will be divided in half after each cycle. It roughly divides the array in half after each attempt to find the target. Binary searches begin by "checking" the middle element in the array. If this matches the target, the position of the element will be returned. If not, the algorithm will restrict the next search attempt to either the upper or lower half of the array being searched depending on where the "target" value falls in the sorted order of the array. This is repeated until the target is found (return array position where found) or every position has been logically checked with target value not found indicating failure. A failure is determined by checking for a "low" position that is greater than the "high" position. When the "low" position has exceeded the "high" position, the array has been ultimately "sealed".
The following C++ function definition can be used to search an array of integers previously sorted into ascending order. Like the linear search, the variable size represents the size of the array. For example, if size equals a value of 100, then the array will store values in positions 0 through 99.
int binarySearch(int arr[], int size, int target)
{
int middlePosition, middleValue, result = -1;
int low = 0, high = size - 1;
bool isFound = 0;
while ( !isFound && low <= high)
{
middlePosition = (low + high) / 2;
middleValue = arr[middlePosition];
if (target == middleValue)
{
result = middlePosition;
isFound = 1;
}
else if (target < middleValue)
high = middlePosition - 1;
else
low = middlePosition + 1;
}
return result;
}
|
Similar to the linear search, when the above C++ function is called, one of two values will be returned: the target's position in the array or a value of -1 indicating failure. The following is the same algorithm written using the ADA programming language.
function binarySearch(arr : tMyArr; target : integer; size : integer) return integer is
result : integer := -1;
low : integer := 0;
high : integer := size-1;
middlePosition, middleValue : integer;
isFound : boolean := FALSE;
begin
while low <= high and not isFound loop
middlePosition := (low + high) / 2;
middleValue := arr(middlePosition);
if target = middleValue then
result := middlePosition;
isFound := TRUE;
elsif target < middleValue then
high := middlePosition - 1;
else
low := middlePosition + 1;
end if;
end loop;
return result;
end binarySearch;
|
Search Efficiency
We now have two algorithms and have written code to handle both methods. Our next step is to determine which method is more efficient for our needs.
Linear Search - For an array of size N, the worst possible case would need N comparisons while searching the array. The average case is (n + 1) / 2 such "attempts".
Binary Search - For an array of size N, there could be at most log base 2 N comparisons.
Consider our product identification problem. Assume we need to track 32,768 products. In such a case, we would need to declare the array to be of size 32768. Using a linear search to find a particular product id, the average case would need
16384.5 comparisons. Using a binary search, we could find the product id in at most 15 comparisons. Comparing 16384.5 with 15, we can easily see a huge difference in program efficiency.
The binary search is extremely efficient compared to the linear search. The fact remains that when dealing with "small" sized arrays, there won't be much difference in program efficiency between the two methods. However, if the array size is "huge", the most efficient method is the binary search. Although a little harder to implement and understand, the binary method is far more beneficial than the linear method for searching arrays.
Program Solution to the Problem
The following complete C++ program illustrates both the linear and binary methods for solving our product identification problem mentioned at the beginning of this article. The code was successfully compiled using Microsoft Visual C++ V.6.
This completes the Techniques for Searching Arrays article. I hope you have found it to be interesting and informative.
Happy coding!
[Back to Top]
|
![[warebiz] :: Programming Bizness](/images/logo.gif){kind=logo}
