Sorting & Binary Search in C++ | Topic 16 | VU Insider



What is sorting is C++?

Suppose we want to sort an array of 100 numbers in an ascending order. There can be several ways like we start from the first number (index 0) and find the smallest in the array. Suppose we find it at number 12 (index 11). If we assign that number directly to the first number, then the number at first position will be overwritten.

But here the problem is we also want replaced number too which is overwritten by number 12. How to overcome this problem? C++ language provides a technique called "Swapping".

Swapping:

It's a technique in which we swap two values with each other. For this purpose, we declare a new variable and assign that value of first variable before assigning second variable to the first variable.

Example:

// assign the value of first position to variable x
x = num [ 0 ];

// assign the value of 12th position to first variable
num [ 0 ] = num [ 11 ];

// assign the value in x to 12th position
num [ 11 ] = x;code-box


* This process is repeated until we get a sorted array.

Binary Search in C++

Binary Search is a method to find a particular element in a sorted array by using "divid and conquer" strategy. It should be noted that this technique can only applies to sorted arrays in ascending or descending order.

This technique is also known as Binary Search Algorithm.

Example:
Suppose we want to search a number from an array of ascending order. For this purpose, we divide the array in half. We will have left and right sides. For example, if you have an array of first 10 numbers, we will have (1-5) in left side and (6-10) on right side. If the required data value is greater than the element at the middle of the array, then the right half of the array is considered. Otherwise, the left half is considered.

This process is done continuously until either the required number/value is obtained or the remaining array is empty.

Visual Representation of Binary Search

Post a Comment

Previous Post Next Post