#sorted array

[techiemedotin]

Build Balanced Binary Search Tree from Array

Build Balanced Binary Search Tree from Array

Introduction

This post describes the algorithm to build binary search tree from array of sorted elements. However, this technique can be used to build balanced binary search tree from array. A balanced binary tree is a binary tree which has minimum height.

To know more about various aspects of a binary search tree, please visit my previous posts.

What does balanced means?

In this post as we are…

View On WordPress

[dchampion24]

[Leetcode]Median of Two Sorted Array

The trickiest part of this problem is to find the median in a O(log(m + n)) runtime complexity. It is natural to think of merging the two sorted arrays first and find the midst element of the merged array. This approach results in an O(n) time and space complexity. It is not that bad, but not good enough to pass this test. 

To reduce time complexity, we must come up with an approach to shrink size of the arrays and avoid traversing every element of them. Actually, this problem is quite similar to the problem "find the k-th element of two sorted arrays". In this case, we just need to find the (m + n)/2-th element with the exactly same approach. 

Before writing code, we must know several facts about the "find the k-th element of two sorted arrays" problem:

When either array is empty, the program should return the k-th element of the other.

When k = 1, the program should return the smaller element between the first elements of the arrays.

If the k/2-th element of array A is smaller than the k/2-th element of array B, i.e. A[k/2 - 1] < B[k/2 - 1], the first k/2 elements can never be larger than the k-th element of A and B, and vice versa. In other word, if A[k/2 - 1] < B[k/2 -1], the first k/2 elements in A should be discarded, and vice versa. 

If the k/2-th elements of A and B are equal, the program should return this element as the k-th element of the two arrays

With this approach, it is always assumed that A is smaller than B in size. Otherwise, k/2 might be out of B's index when A is much larger than B in size. So there must be a line to deal with the situation that A's size is larger than B's. The code is shown below:

Java:

public class Solution { public double findMedianSortedArrays(int[] A, int[] B){ int len = A.length + B.length; if(len % 2 == 1) return (double)findMedian(A, B, 0, 0, len / 2 + 1); else return (findMedian(A, B, 0, 0, len / 2) + findMedian(A, B, 0, 0, len / 2 + 1)) / 2.0; } public int findMedian(int[] A, int[] B, int as, int bs, int k){ int alen = A.length - as, blen = B.length - bs; if(alen > blen) return findMedian(B, A, bs, as, k); if(alen == 0) return B[bs + k - 1]; if(k == 1) return Math.min(A[as], B[bs]); int pa = Math.min(k / 2, alen), pb = k - pa; if(A[as + pa - 1] < B[bs + pb - 1]) return findMedian(A, B, as + pa, bs, k - pa); else if(A[as + pa - 1] > B[bs + pb - 1]) return findMedian(A, B, as, bs + pb, k - pb); else return A[as + pa - 1]; } }

Python:

class Solution: # @return a float def findMedianSortedArrays(self, A, B): total = len(A) + len(B) if total % 2 == 1: return self.findMedian(A, B, total / 2 + 1) / 1.0 else: return (self.findMedian(A, B, total / 2) + self.findMedian(A, B, total / 2 + 1)) / 2.0 def findMedian(self, a, b, k): if len(a) > len(b): return self.findMedian(b, a, k) if len(a) == 0: return b[k - 1] if k == 1: return min(a[0], b[0]) pa = min(k / 2, len(a)) pb = k - pa if a[pa - 1] < b[pb - 1]: return self.findMedian(a[pa:], b, k - pa) elif a[pa - 1] > b[pb - 1]: return self.findMedian(a, b[pb:], k - pb) else: return a[pa - 1]

The algorithm can be improved so that we don't need to concern about if A is smaller than B in size. The improvement is simple: we compare the k/(len(A) + len(B))-th element of A to the counterpart of B, so that it always take away a proper portion of A rather than a fix number of elements. The code is shown below:

Java:

public class Solution { public double findMedianSortedArrays(int[] A, int[] B){ int len = A.length + B.length; if(len % 2 == 1) return (float)findMedian(A, 0, A.length - 1, B, 0, B.length - 1, len / 2); else return (findMedian(A, 0, A.length - 1, B, 0, B.length - 1, len / 2) + findMedian(A, 0, A.length - 1, B, 0, B.length - 1, len / 2 - 1)) / 2.0; } public int findMedian(int[] A, int as, int ae, int[] B, int bs, int be, int k){ int alen = ae - as + 1, blen = be - bs + 1; if(alen == 0) return B[bs + k]; if(blen == 0) return A[as + k]; if(k == 0) return Math.min(A[as], B[bs]); int ak = alen * k / (alen + blen), bk = k - ak - 1; if(A[as + ak] < B[bs + bk]) return findMedian(A, as + ak + 1, ae, B, bs, be, k - ak - 1); else if(A[as + ak] > B[bs + bk]) return findMedian(A, as, ae, B, bs + bk + 1, be, k - bk - 1); else return A[as + ak]; } }

Python:

class Solution: # @return a float def findMedianSortedArrays(self, A, B): total = len(A) + len(B) if total % 2 == 1: return self.findMedian(A, B, total / 2) / 1.0 else: return (self.findMedian(A, B, total / 2) + self.findMedian(A, B, total / 2 - 1)) / 2.0 def findMedian(self, a, b, k): if len(a) == 0: return b[k] if len(b) == 0: return a[k] if k == 0: return min(a[0], b[0]) pa = len(a) * k / (len(a) + len(b)) pb = k - pa - 1 if a[pa] < b[pb]: return self.findMedian(a[pa + 1:], b, k - pa - 1) elif a[pa] > b[pb]: return self.findMedian(a, b[pb + 1:], k - pb - 1) else: return a[pa]

[ictjobs-blog]

New Post has been published on Learning Hub

New Post has been published on http://ictjobs.info/program-construct-balanced-binary-tree-sorted-array/

C Program to Construct a Balanced Binary Tree using Sorted Array

#include <stdio.h> #include <stdlib.h> struct btnode int value; struct btnode *l; struct btnode *r; ; typedef struct btnode N; N* bst(int arr[], int first, int last); N* new(int val); void display(N *temp); int main() int arr[] = 10, 20, 30, 40, 60, 80, 90; N *root = (N*)malloc(sizeof(N)); int n = sizeof(arr) / sizeof(arr[0]), i; printf("Given sorted array is\n"); for (i = 0;i < n;i++) printf("%d\t", arr[i]); root = bst(arr, 0, n - 1); printf("\n The preorder traversal of binary search tree is as follows\n"); display(root); printf("\n"); return 0; /* To create a new node */ N* new(int val) N* node = (N*)malloc(sizeof(N)); node->value = val; node->l = NULL; node->r = NULL; return node; /* To create a balanced binary search tree */ N* bst(int arr[], int first, int last) int mid; N* temp = (N*)malloc(sizeof(N)); if (first > last) return NULL; mid = (first + last) / 2; temp = new(arr[mid]); temp->l = bst(arr, first, mid - 1); temp->r = bst(arr, mid + 1, last); return temp; /* To display the preorder */ void display(N *temp) printf("%d->", temp->value); if (temp->l != NULL) display(temp->l); if (temp->r != NULL) display(temp->r);

Output

Given sorted array is 10 20 30 40 60 80 90 The preorder traversal of binary search tree is as follows 40 - > 20 - > 10 - > 30 - > 80 - > 60 - > 90

[ictjobs-blog]

New Post has been published on Learning Hub

New Post has been published on http://ictjobs.info/program-sort-integer-array-lsdradix-sort-algorithm/

C Program to Sort an Integer Array using LSDRadix Sort Algorithm

#include <stdio.h> int min = 0, count = 0, array[100] = 0, array1[100] = 0; void main() int k, i, j, temp, t, n; printf("Enter size of array :"); scanf("%d", &count); printf("Enter elements into array :"); for (i = 0; i < count; i++) scanf("%d", &array[i]); array1[i] = array[i]; for (k = 0; k < 3; k++) for (i = 0; i < count; i++) min = array[i] % 10; /* To find minimum lsd */ t = i; for (j = i + 1; j < count; j++) if (min > (array[j] % 10)) min = array[j] % 10; t = j; temp = array1[t]; array1[t] = array1[i]; array1[i] = temp; temp = array[t]; array[t] = array[i]; array[i] = temp; for (j = 0; j < count; j++) /*to find MSB */ array[j] = array[j] / 10; printf("Sorted Array (lSdradix sort) : "); for (i = 0; i < count; i++) printf("%d ", array1[i]);

Output

/* Average Case */ Enter size of array : 7 Enter elements into array : 170 45 90 75 802 24 2 Sorted Array ( ladradix sort ) : 2 24 45 75 90 170 802 /* Best case */ Enter size of array : 7 Enter elements into array : 22 64 121 78 159 206 348 Sorted Array ( ladradix sort ) : 22 64 78 159 121 206 348 /* Worst case */ Enter size of array : 7 Enter elements into array : 985 27 64 129 345 325 091 Sorted Array ( ladradix sort ) : 27 64 91 129 325 345 985

[ictjobs-blog]

New Post has been published on Learning Hub

New Post has been published on http://ictjobs.info/program-implement-selection-sort-method-functions/

C Program to Implement Selection Sort Method using Functions

#include <stdio.h> int findmax(int b[10], int k); void exchang(int b[10], int k); void main() int array[10]; int i, j, n, temp; printf("Enter the value of n \n"); scanf("%d", &n); printf("Enter the elements one by one \n"); for (i = 0; i < n; i++) scanf("%d", &array[i]); printf("Input array elements \n"); for (i = 0; i < n ; i++) printf("%d\n", array[i]); /* Selection sorting begins */ exchang(array, n); printf("Sorted array is...\n"); for (i = 0; i < n; i++) printf("%d\n", array[i]); /* function to find the maximum value */ int findmax(int b[10], int k) int max = 0, j; for (j = 1; j <= k; j++) if (b[j] > b[max]) max = j; return(max); void exchang(int b[10], int k) int temp, big, j; for (j = k - 1; j >= 1; j--) big = findmax(b, j); temp = b[big]; b[big] = b[j]; b[j] = temp; return;

Output

Enter the value of n 4 Enter the elements one by one 57 90 34 78 Input array elements 57 90 34 78 Sorted array is... 34 57 78 90

[ictjobs-blog]

New Post has been published on Learning Hub

New Post has been published on http://ictjobs.info/program-accept-sorted-array-search-binary-search/

C Program to accept Sorted Array and do Search using Binary Search

#include <stdio.h> void main() int array[10]; int i, j, num, temp, keynum; int low, mid, high; printf("Enter the value of num \n"); scanf("%d", &num); printf("Enter the elements one by one \n"); for (i = 0; i < num; i++) scanf("%d", &array[i]); printf("Input array elements \n"); for (i = 0; i < num; i++) printf("%d\n", array[i]); /* Bubble sorting begins */ for (i = 0; i < num; i++) for (j = 0; j < (num - i - 1); j++) if (array[j] > array[j + 1]) temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; printf("Sorted array is...\n"); for (i = 0; i < num; i++) printf("%d\n", array[i]); printf("Enter the element to be searched \n"); scanf("%d", &keynum); /* Binary searching begins */ low = 1; high = num; do mid = (low + high) / 2; if (keynum < array[mid]) high = mid - 1; else if (keynum > array[mid]) low = mid + 1; while (keynum != array[mid] && low <= high); if (keynum == array[mid]) printf("SEARCH SUCCESSFUL \n"); else printf("SEARCH FAILED \n");

Output

Enter the value of num 5 Enter the elements one by one 23 90 56 15 58 Input array elements 23 90 56 15 58 Sorted array is... 15 23 56 58 90 Enter the element to be searched 58 SEARCH SUCCESSFUL Enter the value of num 4 Enter the elements one by one 1 98 65 45 Input array elements 1 98 65 45 Sorted array is... 1 45 65 98 Enter the element to be searched 6 SEARCH FAILED

[ictjobs-blog]

New Post has been published on Learning Hub

New Post has been published on http://ictjobs.info/program-sort-numbers-ascending-order-bubble-sort/

C Program to Sort N Numbers in Ascending Order using Bubble Sort

#include <stdio.h> #define MAXSIZE 10 void main() int array[MAXSIZE]; int i, j, num, temp; printf("Enter the value of num \n"); scanf("%d", &num); printf("Enter the elements one by one \n"); for (i = 0; i < num; i++) scanf("%d", &array[i]); printf("Input array is \n"); for (i = 0; i < num; i++) printf("%d\n", array[i]); /* Bubble sorting begins */ for (i = 0; i < num; i++) for (j = 0; j < (num - i - 1); j++) if (array[j] > array[j + 1]) temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; printf("Sorted array is...\n"); for (i = 0; i < num; i++) printf("%d\n", array[i]);

Output

Enter the value of num 6 Enter the elements one by one 23 45 67 89 12 34 Input array is 23 45 67 89 12 34 Sorted array is... 12 23 34 45 67 89