Showing posts with label Data Structures. Show all posts
Showing posts with label Data Structures. Show all posts

Tuesday, February 27, 2018

Sorting algorithms and programs in data structures using C

Sorting algorithms and programs in data structures using C


Sorting Techniques


  • Bubble sort
  • Insertion sort
  • Heap sort
  • Shell sort
  • Merge sort
  • Quick sort
  • Radix sort


different sorting algorithms in data structures
complexity of sorting algorithms
how to sort data efficiently
sorting algorithms comparison

Searching algorithms and programs in data structures using C

Searching algorithms and programs in data structures using C


Searching algorithms


  • Hashing

***********


searching algorithms in data structures
searching algorithms implementation using C
linear search, binary search and hashing techniques 
searching algorithms in C 

Monday, February 26, 2018

Binary search algorithm in data structures using C

Binary search algorithm in data structures

Binary search

Binary search is a search algorithm that works with the concept of divide and conquer. It is a fast search algorithm with the time complexity of O(log n). It requires that the keys in the array should be stored in a sorted order.
Let us assume an array a[] of n elements and the key k to be searched among them. The algorithm finds the middle element of array a[] and compares with the key to be found. If they match, then return the index as result. If not, algorithm divides the array into two halves on the middle element and based on the search key value it searches in one of the sub-arrays. If the key value is smaller than the middle element, then search continues with left sub-array otherwise with the right sub-array. The array is sub-divided recursively until the element is found or the entire array is scanned.

Algorithm:
Step 1: Read the array of keys and the key to be searched as input.
Step 2: Find and compare the middle element of the array with the key to be searched.
Step 3: If the middle matches with the key, then the middle index is returned as result and closes the program.
Step 4: If the middle does not match with the key to be searched, then the algorithm divides the array into two halves.
Step 4a: If the key is greater than middle element, the algorithm omits the lower half of the array and considers only the higher half.
Step 4b: If the key is smaller than the middle element, it considers the lower half. And go to step 2.
Step 5: Repeat steps 2 to 4b until the element is found or all the elements in the array are scanned.

Pseudocode:
int binarySearch(int a[], int low_index, int high_index, int key_to_find)
{
int mid_index;
   While (low_index <= high_index)
   {
     mid_index = (low_index + high_index)/2;
     if(a[mid_index] < key_to_find)
         low_index = mid_index + 1;
     else if(a[mid_index] > key_to_find)
         high_index = mid_index - 1;
     else
         return mid_index;
     }
   }
   return -1;
 }

Algorithm Description:
Algorithm / Pseudocode
Description
1: bSearch (a[], low_index, high_index, key_to_find)
2:  {
3:  int mid_index;
4:  while (low_index <= high_index)
5:  {
6:     mid_index = (low_index + high_index)/2;
7:     if(a[mid_index] < key_to_find)
8:         low_index = mid_index + 1;
9:     else if(a[mid_index] > key_to_find)
10:         high_index = mid_index - 1;
11:     else
12:         return mid_index;
13:   }
14:   return -1;               
15: }



4: if left most index of the array is smaller/equal
to right most index then loop
6: find the middle index
7: if the element stored in middle index < key
8: new low index will be middle + 1 (right half)
9: if middle element > key
10: new high index will be middle -1 (left half)

12: if 7 and 9 are invalid, our result is middle.

14: if the key not found in array return -1


************



Binary search algorithm in data structures
How does binary search algorithm work
Implementation of binary search algorithm








Binary search algorithm implementation using C program

Binary search algorithm implementation using C program

Program:


/* recursive binary search*/
#include<stdio.h>

int bsearch(int [ ],int, int, int); //function declaration

int main( )
{
int a[20], i, low_index, high_index;
int position, total_keys, key_to_find
printf("\nEnter the total number of values:");
scanf("%d", &total_keys);

for(i = 0; i < total_keys; i++)
{
    printf("\nEnter the key elements %d  : ", i);
    scanf("%d", &a[i]);
}
printf("\nEnter the key to search : ");
scanf("%d", &key_to_find);
low_index = 0;
high_index = n-1;
//the following line calls the function bsearch with parameters
position = bsearch(a, key_to_find, low_index, high_index);
if(position!=-1)
    printf("Search successful, element found at position %d", position);
else
    printf("Search unsuccessful, element not found");
getch();
}

int bsearch(int a[ ], int k, int lb, int ub)
{
int mid;
while(ub >= lb) //repeat this loop while upper bound >= lower bound
             {
             mid=(lb+ub)/2; //finds new middle index in each iteration
             if(k < a[mid]) //if the key_to_find is smaller than middle element of array,
                  ub = mid-1; //set the new upper bound as middle-1
             else if(k > a[mid]) //if key_to_find is larger than middle
                  lb = mid+1; //set the new lower bound as middle+1
             else if(k == a[mid]) //if key_to_find is equal to middle element
                  return(mid); //return the middle element as result
             return (bsearch(a,k,lb,ub)); //if none of the above holds, call bsearch (recursive)
}
return -1; //if the key_to_find is not in the list, return -1 to tell ‘NOT FOUND’
}

**************




binary search program in C
binary search algorithm using recursive functions in C
binary search divide and conquer algorithm
binary search simple program in C
 





Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery