[go: up one dir, main page]
Scribd
Upload
6 views5 pages

SEARCHING Reference

The document discusses search algorithms in computer science, focusing on linear and binary search techniques. Linear search checks each item sequentially, while binary search uses a divide and conquer approach on sorted data, significantly reducing the number of comparisons needed. A comparison table highlights the differences in time complexity, prerequisites, and implementation between the two methods.

Uploaded by

badimela1508
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views5 pages

SEARCHING Reference

The document discusses search algorithms in computer science, focusing on linear and binary search techniques. Linear search checks each item sequentially, while binary search uses a divide and conquer approach on sorted data, significantly reducing the number of comparisons needed. A comparison table highlights the differences in time complexity, prerequisites, and implementation between the two methods.

Uploaded by

badimela1508
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

SEARCHING ALGORITHMS

In computer science, a search algorithm is an algorithm that retrieves


information stored within some data structure. Data structures can include
linked lists, arrays, search trees, hash tables, or various other storage
methods. The appropriate search algorithm often depends on the data
structure being searched.

Types of Searching techniques:

1. Linear Search

2. Binary search

1|Page Prepared by CSE DEPARTMENT, RGMCET (AUTONOMUS)


LINEAR SERACH

Linear search is a very simple search algorithm. In this type of search, a


sequential search is made over all items one by one. Every item is checked and
if a match is found then that particular item is returned, otherwise the search
continues till the end of the data collection.

Algorithm
Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

Pseudocode
procedure linear_search (list, value)

for each item in the list

if match item == value

return the item's location

end if
end for
end procedure

Limitation: If the size of the array is large then it consumes much time,
because as it compares the given element with every element of the array.

2|Page Prepared by CSE DEPARTMENT, RGMCET (AUTONOMUS)


BINARY SEARCH

Binary search algorithm works on the principle of divide and conquer.


For this algorithm to work properly, the data collection should be in the sorted
form.

Binary search looks for a particular item by comparing the middle most
item of the collection. If a match occurs, then the index of item is returned. If
the middle item is greater than the item, then the item is searched in the sub-
array to the left of the middle item. Otherwise, the item is searched for in the
sub-array to the right of the middle item. This process continues on the sub-
array as well until the size of the sub-array reduces to zero.

How Binary Search Works?


For a binary search to work, it is mandatory for the target array to be
sorted. We shall learn the process of binary search with a pictorial example.
The following is our sorted array and let us assume that we need to search the
location of value 31 using binary search.

First, we shall determine half of the array by using this formula −

mid = low + (high - low) / 2


Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the
array.

Now we compare the value stored at location 4, with the value being searched,
i.e. 31. We find that the value at location 4 is 27, which is not a match. As the
value is greater than 27 and we have a sorted array, so we also know that the
target value must be in the upper portion of the array.

3|Page Prepared by CSE DEPARTMENT, RGMCET (AUTONOMUS)


We change our low to mid + 1 and find the new mid value again.

low = mid + 1
mid = low + (high - low) / 2
Our new mid is 7 now. We compare the value stored at location 7 with our
target value 31.

The value stored at location 7 is not a match, rather it is less than what we
are looking for. So, the value must be in the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that
it is a match.

We conclude that the target value 31 is stored at location 5.

Advantage: Binary search halves the searchable items and thus reduces the
count of comparisons to be made to very less numbers.

4|Page Prepared by CSE DEPARTMENT, RGMCET (AUTONOMUS)


How Linear search is different from Binary search?

Linear search starts at the beginning of a list of values, and checks 1 by


1 in order for the result you are looking for. A binary search starts in the
middle of a sorted array, and determines which side (if any) the value you are
looking for is on.

COMPARISON LINEAR SEARCH VS BINARY SEARCH

Sr. Comparison Linear Search Binary Search


No.
1 Time Complexity O(N) O (log2 N)
2 Best case time O(1) O(1) Center Element
First Element
3 Prerequisite for an array No prerequisite Array must be in sorted
order

4 Worst case for N = 1000 elements 1000 comparisons Can conclude


required after only 10
comparisons.

5 Can be implemented on Array and Linked list Cannot be


directly
implemented
on linked list

6 Insert operation when we use either search Easily inserted at the end Require
of list processing to
insert at its
proper place
to maintain
sorted list.

7 Algorithm type Iterative in nature Divide and


conquer in
nature

8 Usefulness Easy to use and no need Somehow


for any ordered elements tricky
algorithm and
elements must
be arranged in
order
9 Lines of Code Less More

5|Page Prepared by CSE DEPARTMENT, RGMCET (AUTONOMUS)

You might also like