SEARCHING (Linear, Binary, Interpolation)

•We’ll often work with large amounts of data stored in arrays

•It may be necessary to determine whether an array contains a value that matches a certain key value

•The process of finding a particular element of an array is called searching

Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Based on the type of search operation, these algorithms are generally classified into two categories:

1. Sequential Search: In this, the list or array is traversed sequentially and every element is checked. For example: Linear Search.
2. Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half. For Example: Binary Search.

•Searching is an action to retrieve information based on particular key from some saved information

•Key is used to do record searching which is desired from a set of data list

•Key must be unique, means there must not be any same key in the data

•Example:

  Student data consists of name, nim, gender, address, place and date of birth

  nim is used as key from the data, as it is unique.

•Several types of searching algorithm:

–Linear Search

–Binary Search

–Interpolation Search

LINEAR SEARCH

•Linear search compares each element of the array with the search key.

•Since the array is not in any particular order, it’s just as likely that the value will be found in the first element as in the last

•On average, therefore, the program will have to compare the search key with half the elements of the array

•Algorithm:

   1. n : total record of array x.

2. For each x[i], 0 £  i £ n-1, check whether x[i] = key.

3. If x[i] = key, then the searched data is found in index=i. Finished.

4. If x[i] ¹ key, then continue searching until the last data which is i = n-1.

5. If i= n-1 and x[i] ¹ key, it means the data is not exist in the list, and set index = -1. Finished.

•

BINARY SEARCH

•The linear searching method works well for small or unsorted arrays. However, for large arrays linear searching is inefficient

•If the array sorted, the high-speed binary search technique can be used

•Algorithm:

1. n : total record of array x.

2. left=0,  right= n-1.

3. mid =(int) (left + right)/2.

4. If x[mid]=key then index = mid. Finished.

5. If x[mid]<key then left = mid+1.

6. If x[mid]>key then right = mid-1.

7. If left £ right and x[mid] ¹ key, then repeat point 3.

8. If x[mid] ¹ key then index = -1. Finished.

•

INTERPOLATION SEARCH

•Interpolation search technique is performed on the sorted data

•This searching process is almost similar with binary search technique

•Searching technique is done with the approximate location of the data

•Example:

–If we want to find a name in the phone book, for example the one beginning with the letter T, then we would not look for from the beginning of the book, but we opened it at 2/3 or ¾ of the book.

•Algorithm:

1.In the interpolation search, we'll split the data according to the following formula:

2.If data[mid] = sought data, data has been found, searching is stopped and return mid.

3.If data[mid]!= sought data, repeat point **

4.**Searching is continued while sought data > data[min] and sought data < data[max].

•Algorithm:

5.Looking for a mid value by entering into the interpolation formula

6.If data[mid] > sought data, high = mid – 1

7.If data[mid] < sought data, low = mid + 1

8.It will be looped until the requirements point ** are not met then return (-1), data not found