Data Searching Data Structures

0
22

Image source: codenuclear.com

There are two main ways of searching for a particular data item within a list, the ‘sequential search’ where each value in the array or list is compared with the value searched for until a match is found, or not found. For the sequential search the data can be in any order and since each item in the list is accessed the time taken will always be the same. This is a very inefficient method and so a better approach is to use a ‘binary search’. However, the data must first be sorted into ascending order. Note there are two data values, the data itself and the position within the array, this is known as the key or index. Input a value from those listed. First a comparison is made with the middle array value, if the value to be searched for is greater or less than this central position, the process jumps forward or back. A further comparison is made with the middle value of this smaller group, repeatedly dividing the search area by two until the process is complete.

Image source: Wikipedia.org

The binary search method is best suited to a data list accommodated within the CPU RAM area. Larger disk based files would have to be continually swapped in and out of RAM during the search, considerably slowing the process. Other methods are available which are more applicable to large databases, using mathematical algorithms, to determine the most likely data item position in the file. The formula shows approximately how many comparisons need to be made to binary search a file of a given length, which is considerably faster than a sequential tial search. Make the Main File Size the same as for your array and see how close the search was.

LEAVE A REPLY

Please enter your comment!
Please enter your name here