**Linear search**

In
linear search, we start searching of value from start until the value is not
found or end of file. If it is, then you can stop searching and report that you
have found the record.

Input A[n + 1] and x.

Set i to 1.

Repeat this loop:

If A[i] = x, then exit the loop.

Set i to i + 1.

Return i.

**Complexity:**O(n).

**Pros:**

Serial
searching is excellent if your records are unordered.

Compared
to a binary search, serial searching is a very easy to implement.

**Cons:**

Serial
searching isn’t very efficient. That's because it takes lots of comparisons to
find a particular record in big files, compared to binary searching. It takes
longer on average to find a record in a big file compared to binary searching.

**Example:**For a file of size 2^20, there are 2^20 comparisons required in worst case.

BinarySearch(A[0..N-1], value) {

low = 0

high = N - 1

while (low <= high) {

mid = (low + high)/2

if (A[mid] > value)

high = mid - 1

else if (A[mid] < value)

low = mid + 1

else

return mid

}

return not_found

}

**Complexity:**O(logn).

**Pros:**

Compared
to a linear search, binary searching is a very efficient.

**Example:**For a file of size 2^20, there are 20 comparisons required in worst case.

Comparisons
required: log(2^20) = 20.

**Cons:**

Binary
searching cannot be applied on the unordered array.

It
is little complex to write binary search compare to linear search.

## No comments:

## Post a Comment