UNIT-2

Sorting and Searching

Introduction Sorting and Searching

Sorting Algorithms

Sorting is the process of arranging the elements of an array so that they can be placed
either in ascending or descending order. For example, consider an array A = {A1, A2, A3,
A4, ??An }, the array is called to be in ascending order if element of A are arranged like A1
> A2 > A3 > A4 > A5 > ? >An .

Consider an array;

int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 )

The Array sorted in ascending order will be given as;

A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }

There are many techniques by using which, sorting can be performed. In this section of the
tutorial, we will discuss each method in detail.

Sorting Algorithms

Sorting algorithms are described in the following table along with the description.

SN Sorting Description
Algorithms

1 Bubble Sort It is the simplest sort method which performs sorting by repeatedly
moving the largest element to the highest index of the array. It
comprises of comparing each element to its adjacent element and
replace them accordingly.
As the name suggests, insertion sort inserts each element of the
2 Insertion Sort
array to its proper place. It is a very simple sort method which is used
to arrange the deck of cards while playing bridge.
3 Merge Sort Merge sort follows divide and conquer approach in which, the list is first
divided into the sets of equal elements and then each half of the list is
sorted by using merge sort. The sorted list is combined again to form an
elementary sorted array.

4 Selection Sort Selection sort finds the smallest element in the array and place it on the
first place on the list, then it finds the second smallest element in the
array and place it on the second place. This process continues until all
the elements are moved to their correct ordering. It carries running
time O(n2) which is worst than insertion sort.
Bubble sort Algorithm

Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the
intended order. It is called bubble sort because the movement of array elements is just like
the movement of air bubbles in the water. Bubbles in water rise up to the surface; similarly,
the array elements in bubble sort move to the end in each iteration.

Although it is simple to use, it is primarily used as an educational tool because the

performance of bubble sort is poor in the real world. It is not suitable for large data sets.
The average and worst-case complexity of Bubble sort is O(n2), where n is a number of
items.

Bubble short is majorly used where -

o complexity does not matter

o simple and shortcode is preferred

Algorithm

In the algorithm given below, suppose arr is an array of n elements. The

assumed swap function in the algorithm will swap the values of given array elements.

begin BubbleSort(arr)
for all array elements
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
end BubbleSort

Working of Bubble sort Algorithm

Now, let's see the working of Bubble sort Algorithm.

To understand the working of bubble sort algorithm, let's take an unsorted array. We are
taking a short and accurate array, as we know the complexity of bubble sort is O(n2).

Let the elements of array are -

First Pass
Sorting will start from the initial two elements. Let compare them to check which is greater.
Here, 32 is greater than 13 (32 > 13), so it is already sorted. Now, compare 32 with 26.

Here, 26 is smaller than 36. So, swapping is required. After swapping new array will look
like -

Now, compare 32 and 35.

Here, 35 is greater than 32. So, there is no swapping required as they are already sorted.

Now, the comparison will be in between 35 and 10.

Here, 10 is smaller than 35 that are not sorted. So, swapping is required. Now, we reach at
the end of the array. After first pass, the array will be -

Now, move to the second iteration.

Second Pass
The same process will be followed for second iteration.
Here, 10 is smaller than 32. So, swapping is required. After swapping, the array will be -

Now, move to the third iteration.

Third Pass
The same process will be followed for third iteration.

Here, 10 is smaller than 26. So, swapping is required. After swapping, the array will be -

Now, move to the fourth iteration.

Fourth pass
Similarly, after the fourth iteration, the array will be -
Hence, there is no swapping required, so the array is completely sorted.

Bubble sort complexity

Now, let's see the time complexity of bubble sort in the best case, average case, and worst
case. We will also see the space complexity of bubble sort.

1. Time Complexity

Case Time Complexity

Best Case O(n)

Average Case O(n2)

Worst Case O(n2)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array
is already sorted. The best-case time complexity of bubble sort is O(n).
o Average Case Complexity - It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending. The average case
time complexity of bubble sort is O(n2).
o Worst Case Complexity - It occurs when the array elements are required to be
sorted in reverse order. That means suppose you have to sort the array elements in
ascending order, but its elements are in descending order. The worst-case time
complexity of bubble sort is O(n2).

2. Space Complexity

Space Complexity O(1)

Stable YES

o The space complexity of bubble sort is O(1). It is because, in bubble sort, an extra
variable is required for swapping.
o The space complexity of optimized bubble sort is O(2). It is because two extra
variables are required in optimized bubble sort.

#include<stdio.h>
void print(int a[], int n) //function to print array elements
 {
int i;
for(i = 0; i < n; i++)
{
printf("%d ",a[i]);
}
}
void bubble(int a[], int n) // function to implement bubble sort
{
int i, j, temp;
for(i = 0; i < n; i++)
{
for(j = i+1; j < n; j++)
{
if(a[j] < a[i])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
void main ()
{
int i, j,temp;
int a[5] = { 10, 35, 32, 13, 26};
int n = sizeof(a)/sizeof(a[0]);
printf("Before sorting array elements are - \n");
print(a, n);
bubble(a, n);
printf("\nAfter sorting array elements are - \n");
print(a, n);
}

Output

Insertion Sort Algorithm

Insertion sort works similar to the sorting of playing cards in hands. It is assumed that the
first card is already sorted in the card game, and then we select an unsorted card. If the
selected unsorted card is greater than the first card, it will be placed at the right side;
otherwise, it will be placed at the left side. Similarly, all unsorted cards are taken and put in
their exact place.

The same approach is applied in insertion sort. The idea behind the insertion sort is that first
take one element, iterate it through the sorted array. Although it is simple to use, it is not
appropriate for large data sets as the time complexity of insertion sort in the average case
and worst case is O(n2), where n is the number of items. Insertion sort is less efficient than
the other sorting algorithms like heap sort, quick sort, merge sort, etc.

Insertion sort has various advantages such as -

o Simple implementation
o Efficient for small data sets
o Adaptive, i.e., it is appropriate for data sets that are already substantially sorted.

Now, let's see the algorithm of insertion sort.

Algorithm

The simple steps of achieving the insertion sort are listed as follows -

Step 1 - If the element is the first element, assume that it is already sorted. Return 1.

Step2 - Pick the next element, and store it separately in a key.

Step3 - Now, compare the key with all elements in the sorted array.

Step 4 - If the element in the sorted array is smaller than the current element, then move
to the next element. Else, shift greater elements in the array towards the right.

Step 5 - Insert the value.

Step 6 - Repeat until the array is sorted.

Working of Insertion sort Algorithm

Now, let's see the working of the insertion sort Algorithm.

To understand the working of the insertion sort algorithm, let's take an unsorted array. It
will be easier to understand the insertion sort via an example.

Let the elements of array are -

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending order. So,
for now, 12 is stored in a sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25. Along
with swapping, insertion sort will also check it with all elements in the sorted array.

For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12. Hence,
the sorted array remains sorted after swapping.

Now, two elements in the sorted array are 12 and 25. Move forward to the next elements
that are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.

So, swap them.

Now, elements 12 and 8 are unsorted.

So, swap them too.

Now, the sorted array has three items that are 8, 12 and 25. Move to the next items that
are 31 and 32.

Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.

Move to the next elements that are 32 and 17.

17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted.

Insertion sort complexity

Now, let's see the time complexity of insertion sort in best case, average case, and in worst
case. We will also see the space complexity of insertion sort.

1. Time Complexity
Case Time Complexity

Best Case O(n)

Average Case O(n2)

Worst Case O(n2)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array
is already sorted. The best-case time complexity of insertion sort is O(n).
o Average Case Complexity - It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending. The average case
time complexity of insertion sort is O(n2).
o Worst Case Complexity - It occurs when the array elements are required to be
sorted in reverse order. That means suppose you have to sort the array elements in
ascending order, but its elements are in descending order. The worst-case time
complexity of insertion sort is O(n2).

2. Space Complexity
Space Complexity O(1)

Stable YES

o The space complexity of insertion sort is O(1). It is because, in insertion sort, an

extra variable is required for swapping.

Implementation of insertion sort

Now, let's see the programs of insertion sort in different programming languages.

Program: Write a program to implement insertion sort in C language.

#include <stdio.h>
void insert(int a[], int n) /* function to sort an aay with insertion sort */
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
 while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one
position ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}

void printArr(int a[], int n) /* function to print the array */

{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);

return 0;
}
Output:

Selection Sort Algorithm

In selection sort, the smallest value among the unsorted elements of the array is selected in
every pass and inserted to its appropriate position into the array. It is also the simplest
algorithm. It is an in-place comparison sorting algorithm. In this algorithm, the array is
divided into two parts, first is sorted part, and another one is the unsorted part. Initially, the
sorted part of the array is empty, and unsorted part is the given array. Sorted part is placed
at the left, while the unsorted part is placed at the right.

In selection sort, the first smallest element is selected from the unsorted array and placed
at the first position. After that second smallest element is selected and placed in the second
position. The process continues until the array is entirely sorted.
The average and worst-case complexity of selection sort is O(n2), where n is the number of
items. Due to this, it is not suitable for large data sets.

Selection sort is generally used when -

o A small array is to be sorted

o Swapping cost doesn't matter
o It is compulsory to check all elements

Now, let's see the algorithm of selection sort.

Algorithm

1. Begin
2. for i := 0 to size-2 do //find minimum from ith location to size
3. iMin := i;
4. for j:= i+1 to size – 1 do
5. if array[j] < array[iMin] then
6. iMin := j
7. done
8. swap array[i] with array[iMin].
9. done
10.End

Working of Selection sort Algorithm

Now, let's see the working of the Selection sort Algorithm.

To understand the working of the Selection sort algorithm, let's take an unsorted array. It
will be easier to understand the Selection sort via an example.

Let the elements of array are -

Now, for the first position in the sorted array, the entire array is to be scanned sequentially.

At present, 12 is stored at the first position, after searching the entire array, it is found
that 8 is the smallest value.
So, swap 12 with 8. After the first iteration, 8 will appear at the first position in the sorted
array.

For the second position, where 29 is stored presently, we again sequentially scan the rest of
the items of unsorted array. After scanning, we find that 12 is the second lowest element in
the array that should be appeared at second position.

Now, swap 29 with 12. After the second iteration, 12 will appear at the second position in
the sorted array. So, after two iterations, the two smallest values are placed at the
beginning in a sorted way.

The same process is applied to the rest of the array elements. Now, we are showing a
pictorial representation of the entire sorting process.
Now, the array is completely sorted.

Selection sort complexity

Now, let's see the time complexity of selection sort in best case, average case, and in worst
case. We will also see the space complexity of the selection sort.

1. Time Complexity
Case Time Complexity

Best Case O(n2)

Average Case O(n2)

Worst Case O(n2)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array
is already sorted. The best-case time complexity of selection sort is O(n2).
o Average Case Complexity - It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending. The average case
time complexity of selection sort is O(n2).
 o Worst Case Complexity - It occurs when the array elements are required to be
sorted in reverse order. That means suppose you have to sort the array elements in
ascending order, but its elements are in descending order. The worst-case time
complexity of selection sort is O(n2).

2. Space Complexity
Space Complexity O(1)

Stable YES

o The space complexity of selection sort is O(1). It is because, in selection sort, an

extra variable is required for swapping.

Implementation of selection sort

Now, let's see the programs of selection sort in different programming languages.

Program: Write a program to implement selection sort in C language.

#include <stdio.h>

void selection(int arr[], int n)

{
int i, j, small;

for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
{
small = i; //minimum element in unsorted array

for (j = i+1; j < n; j++)

if (arr[j] < arr[small])
small = j;
// Swap the minimum element with the first element
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
}
}

void printArr(int a[], int n) /* function to print the array */

{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}

int main()
 {
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
selection(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
Output:

After the execution of above code, the output will be -

Merge Sort Algorithm

Merge sort is similar to the quick sort algorithm as it uses the divide and conquer approach
to sort the elements. It is one of the most popular and efficient sorting algorithm. It divides
the given list into two equal halves, calls itself for the two halves and then merges the two
sorted halves. We have to define the merge() function to perform the merging.

The sub-lists are divided again and again into halves until the list cannot be divided further.
Then we combine the pair of one element lists into two-element lists, sorting them in the
process. The sorted two-element pairs is merged into the four-element lists, and so on until
we get the sorted list.

Now, let's see the algorithm of merge sort.

Algorithm

In the following algorithm, arr is the given array, beg is the starting element, and end is
the last element of the array.

1. MERGE_SORT(arr, beg, end)

2.
3. if beg < end
4. set mid = (beg + end)/2
5. MERGE_SORT(arr, beg, mid)
6. MERGE_SORT(arr, mid + 1, end)
7. MERGE (arr, beg, mid, end)
8. end of if
9.
10. END MERGE_SORT
The important part of the merge sort is the MERGE function. This function performs the
merging of two sorted sub-arrays that are A[beg…mid] and A[mid+1…end], to build one
sorted array A[beg…end]. So, the inputs of the MERGE function are A[], beg,
mid, and end.

The implementation of the MERGE function is given as follows -

/* Function to merge the subarrays of a[] */

void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;

int LeftArray[n1], RightArray[n2]; //temporary arrays

/* copy data to temp arrays */

for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];

i = 0, /* initial index of first sub-array */

j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */

while (i < n1 && j < n2)

{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
 i++;
k++;
}

while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}

Working of Merge sort Algorithm

Now, let's see the working of merge sort Algorithm.

To understand the working of the merge sort algorithm, let's take an unsorted array. It will
be easier to understand the merge sort via an example.

Let the elements of array are -

According to the merge sort, first divide the given array into two equal halves. Merge sort
keeps dividing the list into equal parts until it cannot be further divided.

As there are eight elements in the given array, so it is divided into two arrays of size 4.

Now, again divide these two arrays into halves. As they are of size 4, so divide them into
new arrays of size 2.

Now, again divide these arrays to get the atomic value that cannot be further divided.
Now, combine them in the same manner they were broken.

In combining, first compare the element of each array and then combine them into another
array in sorted order.

So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in
the list of two values, put 8 first followed by 25. Then compare 32 and 17, sort them and
put 17 first followed by 32. After that, compare 40 and 42, and place them sequentially.

In the next iteration of combining, now compare the arrays with two data values and merge
them into an array of found values in sorted order.

Now, there is a final merging of the arrays. After the final merging of above arrays, the
array will look like -

Now, the array is completely sorted.

Merge sort complexity

Now, let's see the time complexity of merge sort in best case, average case, and in worst
case. We will also see the space complexity of the merge sort.

1. Time Complexity

Case Time Complexity

Best Case O(n*logn)

Average Case O(n*logn)

Worst Case O(n*logn)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array
is already sorted. The best-case time complexity of merge sort is O(n*logn).
o Average Case Complexity - It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending. The average case
time complexity of merge sort is O(n*logn).
o Worst Case Complexity - It occurs when the array elements are required to be
sorted in reverse order. That means suppose you have to sort the array elements in
ascending order, but its elements are in descending order. The worst-case time
complexity of merge sort is O(n*logn).

2. Space Complexity

Space Complexity O(n)

Stable YES

o The space complexity of merge sort is O(n). It is because, in merge sort, an extra
variable is required for swapping.

Implementation of merge sort

Now, let's see the programs of merge sort in different programming languages.

Program: Write a program to implement merge sort in C language.

#include <stdio.h>

/* Function to merge the subarrays of a[] */

void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;

int LeftArray[n1], RightArray[n2]; //temporary arrays

/* copy data to temp arrays */

for (int i = 0; i < n1; i++)
 LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];

i = 0; /* initial index of first sub-array */

j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */

while (i < n1 && j < n2)

{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}

while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}

void mergeSort(int a[], int beg, int end)

{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
 }

/* Function to print the array */

void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}
Output:

Searching

Searching in data-strucutre refers to the process of finding a desired element in set of

items. The desired element is called "target". The set of items to be searched in, can be any
data-structure like − list, array, linked-list, tree or graph.

Search refers to locating a desired element of specified properties in a collection of items.

We are going to start our discussion using following commonly used and simple search
algorithms.

Linear Search Algorithm

Two popular search methods are Linear Search and Binary Search. So, here we will discuss
the popular searching technique, i.e., Linear Search Algorithm.

Linear search is also called as sequential search algorithm. It is the simplest searching
algorithm. In Linear search, we simply traverse the list completely and match each element
of the list with the item whose location is to be found. If the match is found, then the
location of the item is returned; otherwise, the algorithm returns NULL.
It is widely used to search an element from the unordered list, i.e., the list in which items
are not sorted. The worst-case time complexity of linear search is O(n).

The steps used in the implementation of Linear Search are listed as follows -

o First, we have to traverse the array elements using a for loop.

o In each iteration of for loop, compare the search element with the current array
element, and -
o If the element matches, then return the index of the corresponding array
element.
o If the element does not match, then move to the next element.
o If there is no match or the search element is not present in the given array,
return -1.

Now, let's see the algorithm of linear search.

Linear Algorithm

Linear_Search(a, n, val) // 'a' is the given array, 'n' is the size of given array, 'val' is t
he value to search
Step 1: set pos = -1
Step 2: set i = 1
Step 3: repeat step 4 while i <= n
Step 4: if a[i] == val
set pos = i
print pos
go to step 6
[end of if]
set ii = i + 1
[end of loop]
Step 5: if pos = -1
print "value is not present in the array "
[end of if]
Step 6: exit

Working of Linear search

Now, let's see the working of the linear search Algorithm.

To understand the working of linear search algorithm, let's take an unsorted array. It will be
easy to understand the working of linear search with an example.

Let the elements of array are -

Let the element to be searched is K = 41

Now, start from the first element and compare K with each element of the array.

The value of K, i.e., 41, is not matched with the first element of the array. So, move to the
next element. And follow the same process until the respective element is found.

Now, the element to be

searched is found. So
algorithm will return the index
of the element matched.

Linear Search complexity

Now, let's see the time complexity of linear search in the best case, average case, and worst
case. We will also see the space complexity of linear search.
1. Time Complexity

Case Time Complexity

Best Case O(1)

Average Case O(n)

Worst Case O(n)

o Best Case Complexity - In Linear search, best case occurs when the element we
are finding is at the first position of the array. The best-case time complexity of linear
search is O(1).
o Average Case Complexity - The average case time complexity of linear search
is O(n).
o Worst Case Complexity - In Linear search, the worst case occurs when the
element we are looking is present at the end of the array. The worst-case in linear
search could be when the target element is not present in the given array, and we
have to traverse the entire array. The worst-case time complexity of linear search
is O(n).

The time complexity of linear search is O(n) because every element in the array is
compared only once.

2. Space Complexity

Space Complexity O(1)

o The space complexity of linear search is O(1).

Implementation of Linear Search

Now, let's see the programs of linear search in different programming languages.

Program: Write a program to implement linear search in C language.

#include <stdio.h>
int linearSearch(int a[], int n, int val) {
// Going through array sequencially
for (int i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1;
 }
int main() {
int a[] = {70, 40, 30, 11, 57, 41, 25, 14, 52}; // given array
int val = 41; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = linearSearch(a, n, val); // Store result
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", val);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
1. }
Output

Binary Search Algorithm

Linear Search and Binary Search are the two popular searching techniques. Here we will
discuss the Binary Search Algorithm.

Binary search is the search technique that works efficiently on sorted lists. Hence, to search
an element into some list using the binary search technique, we must ensure that the list is
sorted.

Binary search follows the divide and conquer approach in which the list is divided into two
halves, and the item is compared with the middle element of the list. If the match is found
then, the location of the middle element is returned. Otherwise, we search into either of the
halves depending upon the result produced through the match.

NOTE: Binary search can be implemented on sorted array elements. If the list elements are
not arranged in a sorted manner, we have first to sort them.
Now, let's see the algorithm of Binary Search.

Algorithm

1. Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is

the index of the first array element, 'upper_bound' is the index of the last array element, 'va
l' is the value to search
2. Step 1: set beg = lower_bound, end = upper_bound, pos = - 1
3. Step 2: repeat steps 3 and 4 while beg <=end
4. Step 3: set mid = (beg + end)/2
5. Step 4: if a[mid] = val
6. set pos = mid
7. print pos
8. go to step 6
9. else if a[mid] > val
10. set end = mid - 1
11. else
12. set beg = mid + 1
13. [end of if]
14. [end of loop]
15. Step 5: if pos = -1
16. print "value is not present in the array"
17. [end of if]
18. Step 6: exit

Working of Binary search

Now, let's see the working of the Binary Search Algorithm.

To understand the working of the Binary search algorithm, let's take a sorted array. It will
be easy to understand the working of Binary search with an example.

There are two methods to implement the binary search algorithm -

o Iterative method
o Recursive method

The recursive method of binary search follows the divide and conquer approach.

Let the elements of array are -

Let the element to search is, K = 56

We have to use the below formula to calculate the mid of the array -

1. mid = (beg + end)/2

So, in the given array -

beg = 0

end = 8
mid = (0 + 8)/2 = 4. So, 4 is the mid of the array.

Now, the element to search is found. So algorithm will return the index of the element
matched.

Binary Search complexity

Now, let's see the time complexity of Binary search in the best case, average case, and
worst case. We will also see the space complexity of Binary search.
1. Time Complexity

Case Time Complexity

Best Case O(1)

Average Case O(logn)

Worst Case O(logn)

o Best Case Complexity - In Binary search, best case occurs when the element to
search is found in first comparison, i.e., when the first middle element itself is the
element to be searched. The best-case time complexity of Binary search is O(1).
o Average Case Complexity - The average case time complexity of Binary search
is O(logn).
o Worst Case Complexity - In Binary search, the worst case occurs, when we have
to keep reducing the search space till it has only one element. The worst-case time
complexity of Binary search is O(logn).

2. Space Complexity

Space Complexity O(1)

o The space complexity of binary search is O(1).

Implementation of Binary Search

Now, let's see the programs of Binary search in different programming languages.

Program: Write a program to implement Binary search in C language.

#include <stdio.h>
int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{ mid = (beg + end)/2;
/* if the item to be searched is present at middle */
if(a[mid] == val)
{
return mid+1;
}
/* if the item to be searched is smaller than middle, then it can only be in left subar
ray */
 else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than middle, then it can only be in right sub
array */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array
int val = 40; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", val);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
}
Output

Hashing in DS

How does Hashing in Data Structure Works?

In hashing, the hashing function maps strings or numbers to a small integer value. Hash
tables retrieve the item from the list using a hashing function. The objective of hashing
technique is to distribute the data evenly across an array. Hashing assigns all the elements
a unique key. The hash table uses this key to access the data in the list.
Hash table stores the data in a key-value pair. The key acts as an input to the hashing
function. Hashing function then generates a unique index number for each value stored. The
index number keeps the value that corresponds to that key. The hash function returns a
small integer value as an output. The output of the hashing function is called the hash
value.
Let us understand hashing in a data structure with an example. Imagine you need to
store some items (arranged in a key-value pair) inside a hash table with 30 cells.
The values are: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)
The hash table will look like the following:

Array
Serial Number Key Hash
Index

1 3 3%30 = 3 3

2 1 1%30 = 1 1

3 40 40%30 = 10 10

4 5 5%30 = 5 5

5 11 11%30 = 11 11

6 15 15%30 = 15 15

7 18 18%30 = 18 18

8 16 16%30 = 16 16

9 38 38%30 = 8 8
The process of taking any size of data and then converting that into smaller data value
which can be named as hash value. This hash value can be used in an index accessible in
hash table. This process define hashing in data structure.