What is data searching? How many types of data searching and what is it? What is linear or sequential searching? Difference between linear and binary search?

Data Searching

Searching:

Searching is the process of finding specific data from an array or file. Let's say an array contains the data 5, 3, 7. n is a data, which must be determined whether it is in this array or if it is in any position. Searching is the method by which this answer is derived. There are different methods of searching. The most commonly used methods are:

(A) Linear Search 

(B) Binary Search

(A) Linear Searching or Sequential Sorting: In order to find specific data in the sequential searching method, starting the comparison from the first data of the array and comparing to the last data if necessary, the value of the specific data is found in the array or not. This method takes more searching time. Each data requires comparison. Searching takes less time when the specified data is located at the beginning of the array. The main advantage of this method is that there is no need to sort the primary data before searching.

Sequential searching or linear searching algorithm:

Step-1 : The data to be searched has to be compared with the 1st data of the array.

Step-2: If the specified data is equal, the data is considered to be in the array and the search is completed.

Step-3: If the data is unequal, compare with the 2nd data.

Step-4 : If the two data are equal then the searching work is completed.

Step-5: If the two data are unequal, the third data has to be compared and thus the last data has to be compared to see if the specific data is in the array or not.

Step-6: If the data to be searched does not match with the array, then that data is considered not in the array. Example: Find the data by finding 30 numbers from the following data in sequential method and determine its position in the array. The data are 10, 20, 15, 30, 45, 8

Solution: First the data is stored in the following array.

Data [1] 10

Data [2] [20]

Data[3] 15

Data [4] 30

Data [5] 45

Data [6] 8

Processing Steps:

In the 1st step it was seen whether Data [1] = 30, the two data are not equal. So, 30 data could not be found

In the 2nd step it is seen whether Data [2] = 30, the two data are not equal. So, not found.

In the 3rd step it is seen whether Data [3] = 30, the two data are not equal. So, not found.

In the 4th step it is seen whether Data [4] = 30 or not, the two data are equal. So, found.

So the data 30 is at position four in the array.

Efficiency of Sequential Search Method:

It is difficult to determine how efficiently the sequential sorting method will work. If the data is found in the first comparison, the search ends with a single comparison. Again, if the data in question matches with the last data of the array or if the data in question is not found, the total number of comparisons will be n. Here n is the total number of data in the array. Average number of comparisons if the data found is found will be (n+1)/2 and total number of comparisons will be n if not found.

(B) Binary Searching

Binary searching method is very popular and very important. Searching this way is very convenient when the array contains a lot of data. This method requires less number of times to search for specific data. As a result, the sorting time is less. Usually Log2(n) number of comparisons. If a data array contains 1024 data then this method may require at most Log2(1024)= 10 times comparison. But sequential method may require up to 1024 comparisons.

Two prerequisites for binary searching are--

(i) The data must be in an array.

(ii) Data should be sorted and data should be compared to find specific data. Then you have to find the specific data by comparing the desired (Item) data with this middle (Middle) value.

The algorithm of binary searching is as follows:

Step-1: Find the median data from the array data and compare the target data (which is to be searched) with the median data.

Step-2: If the data to be searched is equal to the median value then the searching task is completed.

Step-3: If the data to be searched is smaller than the middle value then the data of the specified value will be in the first half of the array (from smallest to largest). And if it is greater than the median value then it will be in the second part or second half.

Step-4: In this way, the first and second part of the data have to be searched by following the method from 1 to 3.

Step-5: The array will be small and limited to only 1 data. If no match is found for even one data then the specified data will be missing.

Method of determination of mean value:

First, the data should be sorted from small to large. The formula for finding the median value of an array

Middle= Integer (Low+High) / 2nd term will be middle value.

Example: An array called D has nine data 12, 14, 15, 20, 40,45,50,60,85. Find this data by searching method from the data.

 Solution: The process of finding 45 data in the binary searching method is as follows:

D[1]12

D[2]14

D[3]15

D[4]20

D[5]40

D[6]45

D[7]50

D[8] 60

(i) First the array must be sorted (if not sorted).

(ii) Array has nine data so Low=1 and High =9.

The middle value of the array is middle Integer (low high) /2 = Integer (1 +9)/2 = 5 and D [5] = 40

(iii) Median value is 40. Now the median value is compared with the discussed data 45. Since 40 > 45 the discussion lies in the second half.

Second part data is 45, 50,60,85

In this part, Low = middle + 1 = 5 + 1 = 6 and High = 9. Here is the middle value

middle = Integer(low + high)/2] = Integer [(6 + 9 )/2 = Integer (7.5 = 7 and D[7] = 50

(iv) Now the median data D[7] = 50 will be compared with the discussed data 45. Since 50>45 the data in question is in the first part. The data for this part is 45.

(v) There is data in this section corresponding to the data in question. So, the data in question is in the array and is in position D[6].

The steps are as follows:

(i) 12, 14, 15, 20, 40, 45, 50, 60, 85

(ii) 12,14, 15, 20, 40, 45, 50, 60, 85

(iii) 12, 14, 15, 20, 40, 45, 50, 60, 85

Difference between Sequential or Linear Search and Binary Search:

Sequential or linear search

(i) In the sequential search method, searching starts from the first data in the array and the searching process ends when the specified data is found.

(ii) Sequential method of more number of comparisons is required

(iii) If the array contains 1024 data then at most 1024 comparisons are required to find any data.

(iv) Searching in this method takes more time.

(v) Using this method for a small amount of data.

(vi) The characteristics of the method are relatively simple.

vii) Data sorting is not required before searching.

Binary search:

(i) Binary search method divides the array into two parts. Finding specific data by comparing intermediate numbers

(ii) Binary search method requires less number of comparisons.

(iii) If the array contains 1024 data then search requires at most Log2 (1024) = 10 times of comparison.

(iv) This method takes less time in searching.

(v) It is better to use it for a large number of data cases.

(vi) The characteristics of the method are relatively complex.

 (vii) Data must be sorted before sorting.