0% found this document useful (0 votes)
5 views11 pages

Lecture 3 Array Searching Algorithm

The document provides an overview of linear and binary search algorithms, detailing their mechanisms and complexities. Linear search operates by sequentially checking each element, with a worst-case time complexity of O(n), while binary search requires a sorted array and has a time complexity of O(log2N). Sample code for both algorithms is included to illustrate their implementation.

Uploaded by

mtanveer7706
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
5 views11 pages

Lecture 3 Array Searching Algorithm

The document provides an overview of linear and binary search algorithms, detailing their mechanisms and complexities. Linear search operates by sequentially checking each element, with a worst-case time complexity of O(n), while binary search requires a sorted array and has a time complexity of O(log2N). Sample code for both algorithms is included to illustrate their implementation.

Uploaded by

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

Lecture 3

Array Searching Algorithm

P R E PA R E D B Y:

AKLEMA SHORNA
LECTURER
S O F T WA R E E N G I N E E R I N G D E PA R T M E N T,
D A F F O D I L I N T E R N AT I O N A L U N I V E R S I T Y.
Contents

Linear Search Algorithm and complexity


Binary search Algorithm and complexity
Linear Search and Binary Search
Algorithm

How Linear Search works:


Searching refers to the operation of finding the location
LOC of ITEM in DATA, or printing some message that
ITEM does not appear there.
DATA is a linear array with n elements. The most
intuitive way to search for a given ITEM in DATA is to
compare ITEM with each element of DATA one by one.
That is first we test whether DATA[1 ]=ITEM, and then
we test whether DATA[2 ]=ITEM, and so on. This
method, which traverses DATA sequentially to locate
ITEM, is called linear search or sequential search.
Linear Search and Binary Search
Algorithm

Linear Search Algorithm : A linear array DATA


with N elements and a specific ITEM of information
are given. This algorithm finds the location LOC of
ITEM in the array DATA or sets LOC = Null.
1. Set Variable=ITEM.
2. Set LOC:=0.
3. i=1
4. Repeat while i<=N and A[i] != item
i= i+1
5. If A[i] = item, then :
loc = i
Write : LOC is the location of ITEM.
5.Exit.
Linear Search Complexity

O(n)

Worst Case Analysis (Usually Done)


In the worst case analysis, we calculate upper bound on
running time of an algorithm. We must know the case that
causes maximum number of operations to be executed. For
Linear Search, the worst case happens when the element to
be searched (x in the above code) is not present in the array.
When x is not present, the search() functions compares it with
all the elements of arr[] one by one. Therefore, the worst case
time complexity of linear search would be Θ(n).

Write down how:


Follow Class Lecture
Sample Code (the main part of the
code)

for (c = 0; c < n; c++)


{
if (array[c] == search)
/* if required element found */
{
printf("%d is present at location %d.\n",
search, c+1);
break;
}
}
Linear Search and Binary Search
Algorithm

How Binary Search Works:


It must be sorted array before applying binary
search.
In binary search, we first compare the key with
the item in the middle position of the array. If
there's a match, we can return immediately. If
the key is less than the middle key, then the item
should lie in the lower half of the array; if it's
greater then the item so it must lie in the upper
half of the array. So we repeat the procedure on
the lower (or upper) half of the array.
Linear Search and Binary Search
Algorithm

Binary Search Algorithm :

BINARY(A, LB, UB, ITEM, LOC)


1. loc = 0
2. Set BEG=LB; END=UB
3. While B<=E
4. Mid= [ (B+E)/2]
if item = A[mid] then;
loc = mid [ exit loop]
else if item > A[mid]
B= Mid +1
else
E= mid-1
5. Return loc
6. Exit.
Binary Search Complexity

O(Log2N)
How??
n
n/2
n/4
n/8
………1 or 0
n/2k

Follow Class Lecture


Sample Code (the main part of the
code)

first = 0;
last = n - 1; //n=total length
middle = (first+last)/2;

while (first <= last) {


if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search)
{
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;

middle = (first + last)/2;


}
if (first > last)
printf("Not found! %d is not present in the list.\n", search);
Questions?

You might also like