Data Structures and Algorithms (Binary Search Tree, Insertion Sort and Bubble Sort) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

 

Algorithm For Binary Search

In the binary search method, the collection is repeatedly divided into half and the key element is searched in the left or right half of the collection depending on whether the key is less than or greater than the mid element of the collection.

A simple Binary Search Algorithm is as follows:

1. Calculate the mid element of the collection.
2. Compare the key items with the mid element.
3. If key = middle element, then we return the mid index position for the key found.
4. Else If key > mid element, then the key lies in the right half of the collection. Thus repeat steps 1 to 3 on the lower (right) half of the collection.
5. Else key < mid element, then the key is in the upper half of the collection. Hence you need to repeat the binary search in the upper half.

As you can see from the above steps, in Binary search, half the elements in the collection are ignored just after the first comparison.

Note that the same sequence of steps holds for iterative as well as recursive binary search.

Let’s illustrate the binary search algorithm using an example.

For example, take the following sorted array of 10 elements.

Let’s calculate the middle location of the array.

Mid = 0+9/2 = 4

#1) Key = 21

First, we will compare the key value with the [mid] element and we find that the element value at mid = 21.

Thus we find that key = [mid]. Hence the key is found at position 4 in the array.

#2) Key = 25

We first compare the key value to mid. As (21 < 25), we will directly search for the key in the upper half of the array.

Now again we will find the mid for the upper half of the array.

Mid = 4+9/2 = 6

The value at location [mid] = 25

Now we compare the key element with the mid element. So (25 == 25), hence we have found the key at location [mid] = 6.

Thus we repeatedly divide the array and by comparing the key element with the mid, we decide in which half to search for the key. Binary search is more efficient in terms of time and correctness and is a lot faster too.

Insertion Sort Algorithm

To sort an array of size N in ascending order: 

• Iterate from arr[1] to arr[N] over the array. 
• Compare the current element (key) to its predecessor. 
• If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Bubble Sort Algorithm

• Run a nested for loop to traverse the input array using two variables i and j, such that 0 ≤ i < n-1 and 0 ≤ j < n-i-1
• If arr[j] is greater than arr[j+1] then swap these adjacent elements, else move on
• Print the sorted array

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview

2 year PGDM (E-Business) from Welingkar, Mumbai

4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology

Google and Hubspot Certification

Brain Bench Certification in C++, VC++, Data Structure and Project Management

10 years of Experience in Software Development out of that 6 years 8 months in Wipro

Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds

•