Lesson 1

Array

At the end of the lesson, the students should be able to:

1. understand and design an array application;

2. develop a depth understanding on searching and sorting
algorithms;
3. apply the appropriate algorithms in writing program; and
4. distinguish and compare the performance of searching and sorting
algorithms.

1
Array

In computer science, an array data structure, or simply an array, is a data structure consisting of a
collection of elements, each identified by at least one array index or key. An array is stored such that
the position of each element can be computed from its index tuple by a mathematical formula.

An array is a collection of two or more elements in the memory cells associated with a particular
symbolic name. Array is a data structure used to store collection of data items that are all of the same
type.

An array element is accessed using its index or what we call an array subscript. Every element of an
array occupies memory spaces. The lowest memory address corresponds to the first element; while
the highest memory address corresponds to the last element. Array subscript is enclosed with a
bracket and the value is one greater than the index number of the highest variable you create.

To process data stored in an array, reference each individual element by specifying the array name
and identifying the element desired.

Why we need Array in C Programming?

Consider a scenario where you need to find out the average of 100 integer numbers entered by user.
In C, you have two ways to do this:

1) Define 100 variables with int data type and then perform 100 scanf() operations to store the
entered values in the variables and then at last calculate the average of them.

2) Have a single integer array to store all the values, loop the array to store all the entered values in
array and later calculate the average.

Which solution is better according to you? Obviously the second solution, it is convenient to store same
data types in one single variable and later access them using array index

How to access element of an array in C

You can use array subscript (or index) to access any element stored in array. Subscript starts with 0,
which means arr[0] represents the first element in the array arr.

ONE-DIMENSIONAL ARRAY

Program often use the same type of data. For example, if you want to add 5 integer values and get its
average, you can declare variable separately as shown below:

int num1, num2, num3 num4, num5

in this declaration we use 5 variables.

On the other hand, instead of explicitly defining 5 variables that handles 5 integer values, why don’t
we declare a single variable and define its size to 5.

GENERAL FORM:

data_type array_name[size];

where data_type is the type of data that all the array elements would be, array_name is the name of
the array and size placed between the symbol [and] is the maximum number of elements that the
array will have.

2
The symbol used for accessing an array element are [and]. So, to access num[0], num[1], num[2],
num[3] and num[4], we must declare it as:

int num[5]

In general arr[n-1] can be used to access nth element of an array. where n is any integer number.

For example:

int mydata[20];
mydata[0] /* first element of array mydata*/
mydata[19] /* last (20th) element of array mydata*/

Example of Array In C programming to find out the average of 4 integers

#include <stdio.h>
int main()
{
int avg = 0;
int sum =0;
int x=0;

/* Array- declaration – length 4*/

int num[4];

/* We are using a for loop to traverse through the array

* while storing the entered values in the array
*/
for (x=0; x<4;x++)
{
printf("Enter number %d \n", (x+1));
scanf("%d", &num[x]);
}
for (x=0; x<4;x++)
{
sum = sum+num[x];
}

avg = sum/4;
printf("Average of entered number is: %d", avg);
return 0;
}

Output:

Enter number 1
10
Enter number 2
10
Enter number 3
20
Enter number 4
40
Average of entered number is: 20

Let’s discuss the important parts of the above program:

3
Input data into the array

Here we are iterating the array from 0 to 3 because the size of the array is 4. Inside the loop we are
displaying a message to the user to enter the values. All the input values are stored in the
corresponding array elements using scanf function.

for (x=0; x<4;x++)

{
printf("Enter number %d \n", (x+1));
scanf("%d", &num[x]);
}

Reading out data from an array

Suppose, if we want to display the elements of the array then we can use the for loop in C like this.

for (x=0; x<4;x++)

{
printf("num[%d]\n", num[x]);
}

Various ways to initialize an array

In the above example, we have just declared the array and later we initialized it with the values input
by user. However you can also initialize the array during declaration like this:

int num[5] = {1, 2, 3, 4 ,5};

OR (both are same)

int num[] = {1, 2, 3, 4, 5};

An array which is not initialized always contain garbage values.

C Array – Memory representation

Introduction to Sorting

4
Sorting is nothing but arranging the data in ascending or descending order. The term sorting came into
picture, as humans realised the importance of searching quickly.

There are so many things in our real life that we need to search for, like a particular record in
database, roll numbers in merit list, a particular telephone number in telephone directory, a particular
page in a book etc. All this would have been a mess if the data was kept unordered and unsorted, but
fortunately the concept of sorting came into existence, making it easier for everyone to arrange data
in an order, hence making it easier to search.

Sorting arranges data in a sequence which makes searching easier.

Sorting Efficiency

If you ask me, how will I arrange a deck of shuffled cards in order, I would say, I will start by checking
every card, and making the deck as I move on.

It can take me hours to arrange the deck in order, but that's how I will do it.

Well, thank God, computers don't work like this.

Since the beginning of the programming age, computer scientists have been working on solving the
problem of sorting by coming up with various different algorithms to sort data.

The two main criterias to judge which algorithm is better than the other have been:

Time taken to sort the given data.

Memory Space required to do so.

Different Sorting Algorithms

There are many different techniques available for sorting, differentiated by their efficiency and space
requirements. Following are some sorting techniques:

1. Bubble Sort
2. Insertion Sort
3. Selection Sort
4. Quick Sort
5. Merge Sort

Although it is easier to understand these sorting techniques, but still we suggest you to first learn
about space complexity, Time complexity and the searching algorithms, to warm up your brain for
sorting algorithms.

Bubble Sort Algorithm

5
Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an
array with n number of elements. Bubble Sort compares all the element one by one and sort them
based on their values.

If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first
element of the array with the second element, if the first element is greater than the second element,
it will swap both the elements, and then move on to compare the second and the third element, and so
on.

If we have total n elements, then we need to repeat this process for n-1 times.

It is known as bubble sort, because with every complete iteration the largest element in the given
array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the
water surface.

Sorting takes place by stepping through all the elements one-by-one and comparing it with the
adjacent element and swapping them if required.

Implementing Bubble Sort Algorithm

Following are the steps involved in bubble sort(for sorting a given array in ascending order):

Starting with the first element(index = 0), compare the current element with the next element of the
array.
If the current element is greater than the next element of the array, swap them.
If the current element is less than the next element, move to the next element. Repeat Step 1.

Let's consider an array with values {5, 1, 6, 2, 4, 3}

Below, we have a pictorial representation of how bubble sort will sort the given array.

6
So as we can see in the representation above, after the first iteration, 6 is placed at the last index,
which is the correct position for it.

Similarly after the second iteration, 5 will be at the second last index, and so on.

7
Insertion Sort Algorithm

Consider you have 10 cards out of a deck of cards in your hand. And they are sorted, or arranged in
the ascending order of their numbers.

If I give you another card, and ask you to insert the card in just the right position, so that the cards in
your hand are still sorted. What will you do?

Well, you will have to go through each card from the starting or the back and find the right position for
the new card, comparing it's value with each card. Once you find the right position, you will insert the
card there.

Similarly, if more new cards are provided to you, you can easily repeat the same process and insert
the new cards and keep the cards sorted too.

This is exactly how insertion sort works. It starts from the index 1(not 0), and each index starting from
index 1 is like a new card, that you have to place at the right position in the sorted sub-array on the
left.

Following are some of the important characteristics of Insertion Sort:

1. It is efficient for smaller data sets, but very inefficient for larger lists;
2. Insertion Sort is adaptive, that means it reduces its total number of steps if a partially sorted array
is provided as input, making it efficient;
3. It is better than Selection Sort and Bubble Sort algorithms;
4. Its space complexity is less. Like bubble Sort, insertion sort also requires a single additional
memory space; and
5. It is a stable sorting technique, as it does not change the relative order of elements which are
equal.

How Insertion Sort Works?

8
Following are the steps involved in insertion sort:

1. We start by making the second element of the given array, i.e. element at index 1, the key. The
key element here is the new card that we need to add to our existing sorted set of
cards(remember the example with cards above);
2. We compare the key element with the element(s) before it, in this case, element at index 0:
 If the key element is less than the first element, we insert the key element before the first
element; and
 If the key element is greater than the first element, then we insert it after the first
element.
3. Then, we make the third element of the array as key and will compare it with elements to it's left
and insert it at the right position; and
4. And we go on repeating this, until the array is sorted.

Let's consider an array with values {5, 1, 6, 2, 4, 3}

Below, we have a pictorial representation of how bubble sort will sort the given array.

9
As you can see in the diagram above, after picking a key, we start iterating over the elements to the
left of the key.

We continue to move towards left if the elements are greater than the key element and stop when we
find the element which is less than the key element.

And, insert the key element after the element which is less than the key element.

Selection Sort Algorithm

Selection sort is conceptually the most simplest sorting algorithm. This algorithm will first find the
smallest element in the array and swap it with the element in the first position, then it will find the
second smallest element and swap it with the element in the second position, and it will keep on doing
this until the entire array is sorted.

It is called selection sort because it repeatedly selects the next-smallest element and swaps it into the
right place.

How Selection Sort Works?

Following are the steps involved in selection sort(for sorting a given array in ascending order):

Starting from the first element, we search the smallest element in the array, and replace it with the
element in the first position.
We then move on to the second position, and look for smallest element present in the sub-array,
starting from index 1, till the last index.
We replace the element at the second position in the original array, or we can say at the first position
in the sub-array, with the second smallest element.
This is repeated, until the array is completely sorted.

Let's consider an array with values {3, 6, 1, 8, 4, 5}

Below, we have a pictorial representation of how selection sort will sort the given array.

In the first pass, the smallest element will be 1, so it will be placed at the first position.

Then leaving the first element, next smallest element will be searched, from the remaining elements.

10
We will get 3 as the smallest, so it will then be placed at the second position.

Then leaving 1 and 3(because they are at the correct position), we will search for the next smallest
element from the rest of the elements and put it at third position and keep doing this until array is
sorted.

Finding Smallest Element in a Sub-array

In selection sort, in the first step, we look for the smallest element in the array and replace it with the
element at the first position. This seems doable, isn't it?

Consider that you have an array with following values {3, 6, 1, 8, 4, 5}. Now as per selection sort, we
will start from the first element and look for the smallest number in the array, which is 1 and we will
find it at the index 2. Once the smallest number is found, it is swapped with the element at the first
position.

Well, in the next iteration, we will have to look for the second smallest number in the array. How can
we find the second smallest number? This one is tricky?

If you look closely, we already have the smallest number/element at the first position, which is the
right position for it and we do not have to move it anywhere now. So we can say, that the first element
is sorted, but the elements to the right, starting from index 1 are not.

So, we will now look for the smallest element in the sub-array, starting from index 1, to the last index.

Confused? Give it time to sink in.

After we have found the second smallest element and replaced it with element on index 1(which is the
second position in the array), we will have the first two positions of the array sorted.

Then we will work on the sub-array, starting from index 2 now, and again looking for the smallest
element in this sub-array.

Quick Sort Algorithm

Quick Sort is also based on the concept of Divide and Conquer, just like merge sort. But in quick sort all
the heavy lifting(major work) is done while dividing the array into sub-arrays, while in case of merge
sort, all the real work happens during merging the sub-arrays. In case of quick sort, the combine step
does absolutely nothing.

It is also called partition-exchange sort. This algorithm divides the list into three main parts:

1. Elements less than the Pivot element

2. Pivot element(Central element)
3. Elements greater than the pivot element

Pivot element can be any element from the array, it can be the first element, the last element or any
random element. In this tutorial, we will take the rightmost element or the last element as pivot.

For example: In the array {52, 37, 63, 14, 17, 8, 6, 25}, we take 25 as pivot. So after the first pass, the
list will be changed like this.

{6 8 17 14 25 63 37 52}

Hence after the first pass, pivot will be set at its position, with all the elements smaller to it on its left
and all the elements larger than to its right. Now 6 8 17 14 and 63 37 52 are considered as two
separate sunarrays, and same recursive logic will be applied on them, and we will keep doing this until
the complete array is sorted.

How Quick Sorting Works?

11
Following are the steps involved in quick sort algorithm:

1. After selecting an element as pivot, which is the last index of the array in our case, we divide
the array for the first time;
2. In quick sort, we call this partitioning. It is not simple breaking down of array into 2 sub-arrays,
but in case of partitioning, the array elements are so positioned that all the elements smaller
than the pivot will be on the left side of the pivot and all the elements greater than the pivot
will be on the right side of it;
3. And the pivot element will be at its final sorted position;
4. The elements to the left and right, may not be sorted; and
5. Then we pick sub-arrays, elements on the left of pivot and elements on the right of pivot, and
we perform partitioning on them by choosing a pivot in the sub-arrays.

Let's consider an array with values {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}

Below, we have a pictorial representation of how quick sort will sort the given array.

In step 1, we select the last element as the pivot, which is 6 in this case, and call for partitioning,
hence re-arranging the array in such a way that 6 will be placed in its final position and to its left will
be all the elements less than it and to its right, we will have all the elements greater than it.

12
Then we pick the sub-array on the left and the sub-array on the right and select a pivot for them, in the
above diagram, we chose 3 as pivot for the left sub-array and 11 as pivot for the right sub-array.

And we again call for partitioning.

Merge Sort Algorithm

Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively,
hence consuming less time.

In the last two tutorials, we learned about Selection Sort and Insertion Sort, both of which have a
worst-case running time of O(n2). As the size of input grows, insertion and selection sort can take a
long time to run.

Merge sort , on the other hand, runs in O(n*log n) time in all the cases.

Before jumping on to, how merge sort works and it's implementation, first lets understand what is the
rule of Divide and Conquer?

Divide and Conquer

If we can break a single big problem into smaller sub-problems, solve the smaller sub-problems and
combine their solutions to find the solution for the original big problem, it becomes easier to solve the
whole problem.

Let's take an example, Divide and Rule.

When Britishers came to India, they saw a country with different religions living in harmony, hard
working but naive citizens, unity in diversity, and found it difficult to establish their empire. So, they
adopted the policy of Divide and Rule. Where the population of India was collectively a one big
problem for them, they divided the problem into smaller problems, by instigating rivalries between
local kings, making them stand against each other, and this worked very well for them.

Well that was history, and a socio-political policy (Divide and Rule), but the idea here is, if we can
somehow divide a problem into smaller sub-problems, it becomes easier to eventually solve the whole
problem.

In Merge Sort, the given unsorted array with n elements, is divided into n sub-arrays, each having one
element, because a single element is always sorted in itself. Then, it repeatedly merges these sub-
arrays, to produce new sorted sub-arrays, and in the end, one complete sorted array is produced.

The concept of Divide and Conquer involves three steps:

1. Divide the problem into multiple small problems;

2. Conquer the subproblems by solving them. The idea is to break down the problem into atomic
subproblems, where they are actually solved; and
3. Combine the solutions of the subproblems to find the solution of the actual problem.

13
How Merge Sort Works?

As we have already discussed that merge sort utilizes divide-and-conquer rule to break the problem
into sub-problems, the problem in this case being, sorting a given array.

In merge sort, we break the given array midway, for example if the original array had 6 elements, then
merge sort will break it down into two sub-arrays with 3 elements each.

But breaking the orignal array into 2 smaller sub-arrays is not helping us in sorting the array.

So we will break these sub- arrays into even smaller

sub-arrays, until we have multiple sub-arrays with
single element in them. Now, the idea here is that an
array with a single element is already sorted, so
once we break the original array into sub-arrays
which has only a single element, we have
successfully broken
down our problem
into base problems.

And then we have to merge all

these sorted sub- arrays, step by
step to form one single sorted
array.

Let's consider
an array with values
{14, 7, 3, 12, 9, 11, 6,
12}

Below, we have a
pictorial
representation
of how merge
sort will sort the given
array.

14
In merge sort we follow the following steps:

1. We take a variable p and store the starting index of our array in this. And we take another
variable r and store the last index of array in it;
2. Then we find the middle of the array using the formula (p + r)/2 and mark the middle index as
q, and break the array into two sub-arrays, from p to q and from q + 1 to r index;
3. Then we divide these 2 sub-arrays again, just like we divided our main array and this
continues; and
4. Once we have divided the main array into sub-arrays with single elements, then we start
merging the sub-arrays.

Two dimensional (2D) array

An array of arrays is known as 2D array. The two dimensional (2D) array in C programming is also
known as matrix. A matrix can be represented as a table of rows and columns.

15
Two-dimensional Arrays. A 2D array has a type such as int[][] or String[][], with two pairs of square
brackets. The elements of a 2D array are arranged in rows and columns, and the new operator for 2D
arrays specifies both the number of rows and the number of columns.

For now don’t worry how to initialize a two dimensional array, we will discuss that part later. This
program demonstrates how to store the elements entered by user in a 2d array and how to display the
elements of a two dimensional array.

#include<stdio.h>
int main()
{
/* 2D array declaration*/
int disp[2][3];
/*Counter variables for the loop*/
int i, j;
for(i=0; i<2; i++)
{
for(j=0;j<3;j++)
{
printf("Enter value for disp[%d][%d]:", i, j);
scanf("%d", &disp[i][j]);
}
}

//Displaying array elements

printf("Two Dimensional array elements:\n");
for(i=0; i<2; i++)
{
for(j=0;j<3;j++)
{
printf("%d ", disp[i][j]);
if(j==2)
{
printf("\n");
}
}
}
return 0;
}

Output:

Enter value for disp[0][0]:1

Enter value for disp[0][1]:2
Enter value for disp[0][2]:3
Enter value for disp[1][0]:4
Enter value for disp[1][1]:5
Enter value for disp[1][2]:6

Two Dimensional array elements:

123
456

Initialization of 2D Array
There are two ways to initialize a two Dimensional arrays during declaration.

int disp[2][4] = {
{10, 11, 12, 13},

16
 {14, 15, 16, 17}
};

OR

int disp[2][4] = { 10, 11, 12, 13, 14, 15, 16, 17};

Although both the above declarations are valid, I recommend you to use the first method as it is more
readable, because you can visualize the rows and columns of 2d array in this method.

Things that you must consider while initializing a 2D array

We already know, when we initialize a normal array (or you can say one dimensional array) during
declaration, we need not to specify the size of it. However that’s not the case with 2D array, you must
always specify the second dimension even if you are specifying elements during the declaration. Let’s
understand this with the help of few examples –

/* Valid declaration*/
int num[2][2] = {1, 2, 3 ,4 }

/* Valid declaration*/
int num[][2] = {1, 2, 3 ,4 }

/* Invalid declaration – you must specify second dimension*/

int num[][] = {1, 2, 3 ,4 }

/* Invalid because of the same reason mentioned above*/

int num[2][] = {1, 2, 3 ,4 }

How to store user input data into 2D array

We can calculate how many elements a two dimensional array can have by using this formula:

The array arr[n1][n2] can have n1*n2 elements. The array that we have in the example below is
having the dimensions 5 and 4. These dimensions are known as subscripts. So this array has first
subscript value as 5 and second subscript value as 4.

So the array num[5][4] can have 5*4 = 20 elements.

To store the elements entered by user we are using two for loops, one of them is a nested loop. The
outer loop runs from 0 to the (first subscript -1) and the inner for loops runs from 0 to the (second
subscript -1). This way the the order in which user enters the elements would be num[0][0], num[0][1],
num[0][2]…so on.

#include<stdio.h>
int main()
{
/* 2D array declaration*/
int num[5][4];
/*Counter variables for the loop*/

int i, j;
for(i=0; i<5; i++)
{
for(j=0;j<4;j++)
{
printf("Enter value for num[%d][%d]:", i, j);
scanf("%d", &num[i][j]);
}
}
return 0;

17
}

In above example, I have a 2D array num of integer type. Conceptually you can visualize the above
array like this:

However the actual representation of this array in memory would be something like this:

18
Searching Algorithms

 Linear Search
 Binary Search
 Exponential Search
 Interpolation Search
 Jump Search
 Ternary Search

The searching algorithms are used to search or find one or more than one element from a dataset.
These type of algorithms are used to find elements from a specific data structures.

Searching may be sequential or not. If the data in the dataset are random, then we need to use
sequential searching. Otherwise we can use other different techniques to reduce the complexity.

Linear Search

Linear searching techniques are the simplest technique. In this technique, the items are searched one
by one. This procedure is also applicable for unsorted data set. Linear search is also known as
sequential search. It is named as linear because its time complexity is of the order of n O(n).

The complexity of Linear Search Technique

Time Complexity : O(n)

Space Complexity : O(1)

Input and Output

Input:

A list of data:

20 4 89 75 10 23 45 69

the search key 10

Output:

Item found at location: 4

Begin
for i := 0 to size -1 do
if array[i] = key then
return i
done
return invalid location
End

19
Binary Search

When the list is sorted we can use the binary search technique to find items on the list. In this
procedure, the entire list is divided into two sub-lists. If the item is found in the middle position, it
returns the location, otherwise jumps to either left or right sub-list and do the same process again until
finding the item or exceed the range.

The complexity of Binary Search Technique

Time Complexity : O(1) for the best case. O(log2 n) for average or worst case.
Space Complexity : O(1)

Input and Output

Input:

A sorted list of data: 12 25 48 52 67 79 88 93

The search key 79

Output:

Item found at location: 5

Algorithm

binarySearch(array, start, end, key)

Input − An sorted array, start and end location, and the search key
Output − location of the key (if found), otherwise wrong location.

Begin
if start <= end then
mid := start + (end - start) /2
if array[mid] = key then
return mid location
if array[mid] > key then
call binarySearch(array, mid+1, end, key)
else when array[mid] < key then
call binarySearch(array, start, mid-1, key)
else
return invalid location
End

Exponential search

Exponential search is also known as doubling or galloping search. This mechanism is used to find the
range where the search key may present. If L and U are the upper and lower bound of the list, then L
and U both are the power of 2. For the last section, the U is the last position of the list. For that reason,
it is known as exponential.

After finding the specific range, it uses the binary search technique to find the exact location of the
search key.

20
The complexity of Exponential Search Technique

Time Complexity : O(1) for the best case. O(log2 i) for average or worst case. Where i is the
location where search key is present.
Space Complexity : O(1)

Input and Output

Input:

A sorted list of data:

10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995

The search key 780

Output:

Item found at location: 16

Algorithm

binarySearch(array, start, end, key)

Input: An sorted array, start and end location, and the search key
Output − location of the key (if found), otherwise wrong location.

Begin
if start <= end then
mid := start + (end - start) /2
if array[mid] = key then
return mid location
if array[mid] > key then
call binarySearch(array, mid+1, end, key)
else when array[mid] < key then
call binarySearch(array, start, mid-1, key)
else
return invalid location
End

exponentialSearch(array, start, end, key)

Input: An sorted array, start and end location, and the search key

Output: location of the key (if found), otherwise wrong location.

Begin
if (end – start) <= 0 then
return invalid location
i := 1
while i < (end - start) do
if array[i] < key then
i := i * 2 //increase i as power of 2
else

21
 terminate the loop
done
call binarySearch(array, i/2, i, key)
End
Interpolation Search

For the binary search technique, the lists are divided into equal parts. For the interpolation searching
technique, the procedure will try to locate the exact position using interpolation formula. After finding
the estimated location, it can separate the list using that location. As it tries to find exact location
every time, so the searching time reduces. This technique can find items easily if the items are
uniformly distributed.

The complexity of Interpolation Search Technique

Time Complexity : O(log2(log2 n)) for the average case, and O(n) for the worst case (when items
are distributed exponentially)
Space Complexity : O(1)

Input and Output

Input:

A sorted list of data:

10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995

The search key 780

Output:

Item found at location: 16

Algorithm

interpolationSearch(array, start, end, key)

Input − An sorted array, start and end location, and the search key
Output: location of the key (if found), otherwise wrong location.

Begin
while start <= end AND key >= array[start] AND key <= array[end] do
dist := key – array[start]
valRange := array[end] – array[start]
fraction := dist / valRange
indexRange := end – start
estimate := start + (fraction * indexRange)
if array[estimate] = key then
return estimate position
if array[estimate] < key then
start := estimate + 1
else
end = estimate -1
done
return invalid position
End

22
Jump Search

Jump search technique also works for ordered lists. It creates a block and tries to find the element in
that block. If the item is not in the block, it shifts the entire block. The block size is based on the size of
the list. If the size of the list is n then block size will be √n. After finding a correct block it finds the item
using a linear search technique. The jump search lies between linear search and binary search
according to its performance.

The complexity of Jump Search Technique

Time Complexity : O(√n)

Space Complexity : O(1)

Input and Output

Input:

A sorted list of data:

10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995

The search key 356

Output:

Item found at location: 11

Algorithm

jumpSearch(array, size, key)

Input: An sorted array, size of the array and the search key
Output − location of the key (if found), otherwise wrong location.

Begin
blockSize := √size
start := 0
end := blockSize
while array[end] <= key AND end < size do
start := end
end := end + blockSize
if end > size – 1 then
end := size
done
for i := start to end -1 do
if array[i] = key then
return i
done
return invalid location
End

23
Ternary Search

Like the binary search, it also separates the lists into sub-lists. This procedure divides the list into three
parts using two intermediate mid values. As the lists are divided into more subdivisions, so it reduces
the time to search a key value.

The complexity of Ternary Search Technique

Time Complexity : O(log3 n)

Space Complexity : O(1)

Input and Output

Input:

A sorted list of data: 12 25 48 52 67 79 88 93

The search key 52

Output:

Item found at location: 3

Algorithm

ternarySearch(array, start, end, key)

Input − An sorted array, start and end location, and the search key
Output − location of the key (if found), otherwise wrong location.

Begin
if start <= end then
midFirst := start + (end - start) /3
midSecond := midFirst + (end - start) / 3
if array[midFirst] = key then
return midFirst
if array[midSecond] = key then
return midSecond
if key < array[midFirst] then
call ternarySearch(array, start, midFirst-1, key)
if key > array[midSecond] then
call ternarySearch(array, midFirst+1, end, key)
else
call ternarySearch(array, midFirst+1, midSecond-1, key)
else
return invalid location
End

24