Main Menu

Our Partners


Authorized Pearson Vue Test Center



TESDA
Live Online Training


Live CCNA Remote lab

Contest

  

CNCTC Articles - Excellence in IT TRAINING

Techniques on How to Search Data from a Database or List

by: Kenneth Tello | 29 Dec, 2010 23:14:54

Article Word Count: | Viewed: times


Learn the basics of linear and binary search algorithms

One of the most important features of every website or system is allowing users to search for particular information within the program; be it product model on an e-commerce site, a particular user for social networking site, or a book title on a library information system. Providing such a feature on your website saves users, visitors and potential customers the burden of taking too much time finding a piece of information on your website. In simple words, a system or website with search feature is user friendly.

Now as programmer, the burden on how to implement search function is in your hands. You need to remember one key point: “searching alone is not enough, what users need is a search feature with fast turnaround time and retrieve relevant results”. To achieve these, you need a searching algorithm that is fully optimized and is robust enough to satisfy all input scenarios. In this article, I will explain the two searching algorithms commonly used in searching data from a database and other data structure such as arrays, lists etc: the linear or sequential search, and the binary search.

Sequential Search

Linear search or sequential search is a searching algorithm in which a particular key or value is linearly searched from a database or list; comparing the input value with each of the element in the list. This process continues until there is a match, otherwise “not found” is returned. Sequential search is considered to be the simplest searching algorithm as it works on a straightforward fashion – a special type of brute force search.

             void sequential_search (int a[ ],int key,int n)

             {

                     loop:

                     {

                           if(a[ i ] equals key)

                           {

                               get the index

                               break;

                           }

                           else{

                                    Increment;

                           }

                     }

             }

Sequential search technique has different running times based on three conditions: best case, average case and worst case. Best case scenario is when the data to be searched is at the beginning of the list or at the first index. Only one comparison is needed, thus sequential search has a running time of O(1) in best case. On the worst case, the needed comparison is equal to the number of elements in the list or rows in a database, thus sequential search has a running time of O(n) where n is the number of elements. On average (which most inputs belong with this case), the number of comparisons needed is approximately half the number of elements.

Sequential search is ideal for systems where data is not sorted or the data are randomly arranged.

Binary Search

Binary search is another searching technique commonly used in wide variety of applications. Binary search works on a different way compared to the sequential search. In fact, there is only one type of data in which binary search is applicable, and that is sorted data. Binary search works by comparing the input value with the value in the middle of the list, if the value of the middle is less than the input value, the search continues by traversing the right side of the list, otherwise the search continues by traversing the left side of the list.

                  void binary_search (int value[ ],int key,int n)

                   {

                       int l=0;

                       int r=n-1;

                       int mid, index;

                          loop:

                              mid = (l+r)/2;

                               if( key equals value[mid] ){

                                    index=mid;

                                    break;

                               }

                               else if (key> value[mid]){

                                     l= mid+1;

                               }

                               else{

                                     r=mid-1;

                               }

                         }

Binary search has the same running time with the sequential search given the best case scenario, which is O(1) (a match is found in the middle of the list) as 1 comparison is needed to find a match. On both average and worst case scenarios, since the values to be traversed are divided into two, thus the running time of binary search in worst case scenario is O(log2n).

However if binary search is used in unsorted list, it’ll have different running time, which is a lot slower than in sorted data. That’s why binary search is mostly used when the data are already sorted.

Which is better?

It depends on the type of data; if you are searching from unsorted data, then linear or sequential searching is better, otherwise implement binary search for sorted data.


Protected by Copyscape Originality Checker





Other Related Topics..
« Prev item - Next Item »
---------------------------------------------


What do you think?

Leave comment

This item is closed, it's not possible to add new comments to it or to vote on it

Comments


your binary search cannot detect if an element is not found

  
CNCTC Live Chat Inquiry

Job Openings

Subscribe

Stay Informed Subscribe

Name *

Email *