Skip to main content

Posts

Showing posts with the label Computer Science

In-place and Out-of-place Algorithms

Algorithms in Computer Science are classified into various categories depending on diverse characteristics of the algorithms and also on the resource usage of them. In-place and out-of-place are one of such categorization depending on the extra memory space used by an algorithm to solve a problem. Let us consider each one separately. In-place algorithms In-place algorithms convert the input in to an output without allocating extra memory space for the process of problem solving. It uses the available space given as the input and replaces input with output. An in-place algorithm can use some small amount of non-constant additional memory. The additional space of O (log n) is the accepted limit but sometimes lower than O(n) is also approved. Bubble sort and Selection sort are two in-place algorithms in the context. Out-of-place algorithms An out-of-place algorithm is the opposite of in-place and needs growing amount of memory (usually O(n) or bigger than that) to process the input into o...

Binary Search Implementation in JavaScript.

Searching algorithms are one of the main categories of algorithms in Computer Science which are studied by novice programmers and students as a preparation for their journeys ahead to become skilled programmers. This post contains a short yet, a composite description on Binary Search algorithm and an implementation written using JavaScript language. Let’s just start! Happy learning :). Binary Search is one of the most popular searching algorithms. It is easy to grasp the knowledge on this algorithm intuitively. It is a divide-and-conquer algorithm, that divides the input array roughly in half every time it checks whether an element of the array is the one, we’re looking for. Binary search has a complexity of O(log n) in the worst case and O(1) in the best case. Note: The input for a binary search algorithm should be a sorted list. Below is an iterative approach to implement a binary search in JavaScript. function binarySearch (sortedArray, key) { let high = sortedArray.length-1 le...