Searching Data.

There are two main methods for searching arrays and these are the Linear search and the Binary search.

• The linear search involves simply starting at the first index and checking each following index sequentially until a certain value is found or the end of the array is reached. A repeat loop construct would be the most useful type of loop used for linear searching.

Linear Search Algorithm

found = false
output "What number are you looking for you"
input x
for i = 1 to n
if Array[i] = x then 
  output "x found at location ";i
  found = true
end if
next i
if found = false then
  output "number not found."
endif

• A binary search is more complex and will only work if the numbers are sorted from highest to lowest or lowest to highest. The binary search divides the array into two parts and examines the item at this mid-way point. If the value being searched for is not at the centre of the split, then the algorithms determines whether the search item is higher or lower than the item found at the mid-way point. The selected half is then halved again and this continues until the value is found or there are no more elements in the array to be checked. This method may seem like a waste of time but it would be much faster than a linear search where large amounts of ordered data are to be searched such as large databases (for example a telephone directory would be opened at half way, and then continuously searched by halving to find the name, rather than starting at the beginning and laboriously checking each name sequentially until the name is found).

Binary Search Algorithm

low = 0;
high = length of array
found = false
output "What number are you looking for you"
input x
while (low <= high)
 middle = ( low  + high ) / 2;
 if( x == array[  middle ]) then
   Output "Item found at location "; middle
   Found = True
 else if( x < array[ middle ]) then
     high = middle - 1;      //search low end of array
   else
     low = middle + 1;		//search high end of array
   end if
 end if
loop
If (found = False) then
 Output "Item not found"
End if