Binary Search

Searching is required for extracting a specific data from a data structure. Binary Search is an efficient technique of searching data from sorted structures. It is very much like searching a particular page in a book.
Let us consider a book having 100 pages. We need to search, say, page 36. We proceed as follows:

1. We divide the book in half and open the middle page. Here it is page 50. We see that our search page has a lower value than this page, so we discard the pages from 51 to 100 and take the first half in consideration.
2. We open the middle page of this portion (page 1 - page 50). Here it is page 25. We see that  our search page has a higher value than this page, so we discard the pages from 1 to 25 and take the second half in consideration.
3. We open the middle page of this portion (page 26 - page 50). Here it is page 38. We see that  our search page has a lower value than this page, so we discard the pages from 39 to 50 and take the first half in consideration.
4. We open the middle page of this portion (page 26 - page 38). Here it is page 33. We see that  our search page has a higher value than this page, so we discard the pages from 26 to 33 and take the second half in consideration.
5. We open the middle page of this portion (page 34 - page 38). Here it is page 36. This is our search page and we have found it.

This same method is applied to a sorted array to find a particular entry in the array. A graphical representation  of Binary Search is given below.

Fact:

Worst-case performance is O(log n) and best-case performance is O(1), where n is the total number of elements in the array.

Now, the Binary Search algorithm can be implemented either by using an iterative procedure or by a recursive procedure. Since the recursive procedure is better and more efficient among the two, I am providing the source code of the recursive procedure only.

Note: It is assumed that the user will enter the data in ascending order of values; otherwise the array will have to be explicitly sorted in the program.

Program Listing:

#include <stdio.h>

#include <conio.h>

int arr[50],num; // Global declaration of the array and number to be searched

void BSearch(int low,int high)

{

int mid=(high+low)/2;

if(low>=high) // Breaking condition

{

printf("\n%d is not present in array",num);

return;

}

else if(arr[mid]==num) // Breaking condition

{

printf("\n%d is present in array",num);

return;

}

else if(arr[mid]<num)

BSearch(mid+1,high);

else if(arr[mid]>num)

BSearch(low,mid-1);

}

void main()

{

int n,i;

printf("How many numbers will you enter? (<=50): ");

scanf("%d",&n);

for(i=0;i<=n-1;i++)

{

printf("Enter #%d: ",i+1);

scanf("%d",&arr[i]);

}

printf("\nEnter number to search: ");

scanf("%d",&num);

BSearch(0,n-1); // Call to the Binary Search function

getch();

}

Output:

How many numbers will you enter? (<=50): 5

Enter #1: 12

Enter #2: 45

Enter #3: 56

Enter #4: 78

Enter #5: 92

Enter number to search: 78

78 is present in array

So you thought you knew everything about computers...

Once a programmer asked a user to send the programmer a copy of his floppy.
An express package arrived the next day containing a Xerox photocopy of the
floppy. But the user was not completely computer-illiterate: He knew it was a
two-sided floppy, so he had photocopied both sides.

Sorting Techniques: Selection Sort

I'll start with Selection Sort as my first program here. Sorting is required in various data organising procedures and Selection Sort is one algorithm among several sorting algorithms available. The algorithm is given in the diagram below.



Fact:
In worst-case scenario, Selection Sort makes n(n-1)/2 [Worst-case runtime: Θ(n²)] number of swappings, if n be the total number of elements to be sorted.













Program listing:

/*Program to selection-sort array elements in descending order*/

#include <stdio.h>

#include <conio.h>

void SSort(int num[],int n)

{

int j,k,t;

for(j=0;j<=n-2;j++)

{

for(k=j+1;k<=n-1;k++)

if(num[j]<num[k]) // For ascending order check num[j]>num[k]

{

/*Swapping elements*/

t=num[j];

num[j]=num[k];

num[k]=t;

}

}

}

void main()

{

int num[50],n,i;

clrscr(); // Replace by system("cls") in Visual Studio

printf("How many numbers will you enter? (<=50) ");

scanf("%d",&n);

for(i=0;i<=n-1;i++)

{

/*Entering Data in array*/

printf("Enter #%d ",i+1);

scanf("%d",&num[i]);

}

SSort(num,n);

printf("\nSorted Order:");

for(i=0;i<=n-1;i++)

printf("\n#%d: %d",i+1,num[i]);

getch();

}

Output:

How many numbers will you enter? (<=50) 5

Enter #1 56

Enter #2 78

Enter #3 45

Enter #4 12

Enter #5 92

Sorted Order:

#1: 92

#2: 78

#3: 56

#4: 45

#5: 12

Introduction

Hello everyone,
I am Asmit. I am currently pursuing B.Tech in Computer Science and Engineering at National Institute of Technology, Durgapur. 'Interest Yourself' mainly focuses on programming. I will be sharing with you common programs that high school and college students learning programming have in their curriculum. I will also be sharing some interesting programs that I've written. I will be primarily using C or C++. With time, I'll try to improve the contents.