Darinka Zobenica

Dimitrije Stamenic

Structural Design Patterns in Python

<h2 id="introduction">Introduction</h2>
In this article, we'll discuss a concept related to serialization and deserialization in Java. Although sometimes considered as &quot;<a rel="nofollow noopener" target="_blank" href="https://stackoverflow.com/a/21562563/5943138">part of the black magic of the Java serialization API</a>&quot;, in this article we'll see that <code>serialVersionUID</code> is in fact quite straightforward and simple.
First, we'll gloss over serialization and deserialization to recollect some important ideas that we're going to need later on. Afterwards, we'll dive deeper into <code>serialVersionUID</code> and show what it is and how it works.
Finally, we'll conclude by showing an example which should tie everything together.
<h2 id="serializationanddeserialization">Serialization and Deserialization</h2>
Serialization is the process of storing the state of an object so that it can be persisted into a database, transferred over the network, written into a file, etc. How exactly does serialization work is beyond the scope of this article, but in general - it works by converting the object into a byte stream which can then be used as any other stream of information, e.g. transferred through a network socket.
Deserialization is the process opposite to serialization. It takes the byte-stream representation of an object (e.g. from a file or a socket) and converts it back into a Java object that lives inside the JVM.
Before either serialization or deserialization can be performed on an object, it is necessary that this object (i.e. its class) implements the <code>Serializable</code> interface. The <code>Serializable</code> interface is used to &quot;mark&quot; classes which can be (de)serialized.
Without a class implementing this interface, it's not possible to either serialize or deserialize objects from that class. In the words of the <a rel="nofollow noopener" target="_blank" href="https://docs.oracle.com/javase/7/docs/api/java/io/Serializable.html">Serializable Javadoc</a>:
<blockquote>
&quot;Serializability of a class is enabled by the class implementing the java.io.Serializable interface*.
</blockquote>
<h2 id="whatistheserialversionuid">What is the serialVersionUID?</h2>
For serialization and deserialization to work properly, each serializable class must have a version number associated with it - the serialVersionUID. The purpose of this value is to make sure that the classes used both by the sender (the one that serializes) and the receiver (the one that deserializes) of the serialized object are compatible with each other.
If we think about this, it makes much more sense. There should be some mechanism of determining whether the object that was sent matches the object that was received. Otherwise, it could happen, for example, that a change was made to the class of an object before its serialization which the receiver isn't aware of.
Upon reading the object (i.e. deserialization), the reader could load the &quot;new&quot; object into the &quot;old&quot; representation. This could have annoying consequences at best, and complete disarray of the business logic at worst.
That's precisely the reason why the <code>serialVersionUID</code> exists and is typically used with all serializable objects. It is used to verify that both &quot;versions&quot; of an object (at the sender's and the receiver's side) are compatible, i.e. identical.
In case an update indeed needs to be made to the class, this can be denoted by incrementing the value of the <code>serialVersionUID</code>. The serialized version will thus have an updated UID which will be stored together with the object and delivered to the reader.
If the reader doesn't have the newest version of the class, an <code>InvalidClassException</code> will be thrown.
<h2 id="howtogenerateserialversionuid">How to Generate serialVersionUID?</h2>
As per the documentation, each serialVersionUID field must be <code>static</code>, <code>final</code>, and of type <code>long</code>. The <a target="_blank" href="https://stackabuse.com/access-modifiers-in-java/">access modifier</a> can be arbitrary, but it is strongly recommended that all declarations use the <code>private</code> modifier.
In that case, the modifier will only apply to the current class and not its subclasses which is the expected behavior; we don't want a class to be influenced by anything else other than itself. With all that said, this is how a properly constructed <code>serialVersionUID</code> might look like:
<pre><code class="hljs">private static final long serialVersionUID = 42L;
</code></pre>
Earlier we mentioned that all serializable classes must implement the <code>Serializable</code> interface.
This interface suggests that all serializable classes can declare a <code>serialVersionUID</code>, but are not obliged to. In case a class doesn't have an explicitly declared serialVersionUID value, one will be generated by the serialization runtime.
<blockquote>
However, it is strongly recommended that all serializable classes explicitly declare a <code>serialVersionUID</code> value.
</blockquote>
This is because the default, the <code>serialVersionUID</code> computation is complex, and thus sensitive to very slight differences in environments. If two different compilers are used in the serialization-deserialization process, an <code>InvalidClassException</code> may be thrown during deserialization because the classes will seemingly not match even though they contain the same contents, verbatim.
Finally, if there are any <code>transient</code> or <code>static</code> fields present in the class, they will be ignored during the serialization process and will be <code>null</code> after deserialization.
<h2 id="serialversionuidexample">serialVersionUID Example</h2>
Let's define a class that we'll be using for serialization and deserialization. Of course, it'll implement the <code>Serializable</code> interface and we'll start off with the <code>serialVersionUID</code> being <code>1</code>:
<pre><code class="hljs">public class Spaceship implements Serializable {

 private static final long serialVersionUID = 1L;

 private Pilot pilot;
 private Engine engine;
 private Hyperdrive hyperdrive;

 public void fly() {
 System.out.println(&quot;We&#x27;re about to fly high among the stars!&quot;);
 }

 // Constructor, Getters, Setters
}
</code></pre>
Next, we'll implement a <code>serializeObject()</code> method which will be responsible for serializing the object and writing it out to a <code>.ser</code> file:
<pre><code class="hljs">public void serializeObject(Spaceship spaceship) {
 ObjectOutputStream out = new ObjectOutputStream(
 new FileOutputStream(&quot;./spaceship.ser&quot;)
 );

 out.writeObject(spaceship);
 out.close();
}
</code></pre>
Our method serializes the <code>spaceship</code> object into a <code>.ser</code> file via a <code>FileOutputStream</code>. This file now contains the serialized contents of our object.
Now, let's implement a <code>deserializeObject()</code> method, which takes in that <code>.ser</code> file and constructs an object back from it:
<pre><code class="hljs">public void deserializeObject(String filepath) {
 Spaceship ship;

 ObjectInputStream in = new ObjectInputStream(
 new FileInputStream(filepath)
 );
 
 ship = (Spaceship) in.readObject();
 in.close();

 ship.fly();
}
</code></pre>
Let's call these two and observe the output:
<pre><code class="hljs">public class Main {
 public static void main(String[] args) {
 Spaceship spaceship = new Spaceship();
 serializeObject(spaceship);
 deserializeObject(&quot;./spaceship.ser&quot;);
 }
}
</code></pre>
This will result in:
<pre><code class="hljs">We&#x27;re about to fly high among the stars!
</code></pre>
Our <code>deserializeObject()</code> method loaded the serialized file into the JVM and successfully converted it into a <code>Spaceship</code> object.
To demonstrate the problem mentioned earlier regarding versioning - let's change the value of the <code>serialVersionUID</code> from <code>1L</code> to <code>2L</code> in our <code>Spaceship</code> class.
Afterwards, let's modify our <code>main()</code> method to read the file again, without writing it with the modified <code>serialVersionUID</code>:
<pre><code class="hljs">public class Main {
 public static void main(String[] args) {
 deserializeObject(&quot;./spaceship.ser&quot;);
 }
}
</code></pre>
Of course, this will result in:
<pre><code class="hljs">Exception in thread &quot;main&quot; java.io.InvalidClassException ...
</code></pre>
As expected, the reason for the exception lies in the <code>serialVersionUID</code>.
Because we haven't written the new data after updating the <code>serialVersionUID</code> value to <code>2L</code>, the serialized object still contains <code>1L</code> as its <code>serialVersionUID</code>.
However, the <code>deserializeObject()</code> method was expecting this value to be <code>2L</code> because that is the actual new value from within the <code>Spaceship</code> instance. Due to this inconsistency between the stored and the restored state of the <code>Spaceship</code> object, the exception was appropriately thrown.
<h2 id="conclusion">Conclusion</h2>
Serialization and deserialization are powerful and common techniques used for storing or transmitting data structures and objects. Sometimes it's easy to overlook certain important details such as the <code>serialVersionUID</code>, especially given the fact that IDEs typically generate it automatically.
Hopefully, it should be a bit more clear now what its purpose is and how to use it properly in the projects to come.

Luka Čupić

In this tutorial, we'll explain what is the serialVersionUID in Java and run through an example of serialization and deserialization using it.

What is the serialVersionUID in Java?

<h2 id="introduction">Introduction</h2>
Just like with all other types of files, you can use the Pandas library to read and write Excel files using Python as well. In this short tutorial, we are going to discuss how to read and write Excel files via <code>DataFrame</code>s.
In addition to simple reading and writing, we will also learn how to write multiple <code>DataFrame</code>s into an Excel file, how to read specific rows and columns from a spreadsheet, and how to name single and multiple sheets within a file before doing anything.
If you'd like to learn more about other file types, we've got you covered:
<ul>
<li><a target="_blank" href="/reading-and-writing-json-files-in-python-with-pandas/">Reading and Writing JSON Files in Python with Pandas</a></li>
<li><a target="_blank" href="/reading-and-writing-csv-files-in-python-with-pandas/">Reading and Writing CSV Files in Python with Pandas</a></li>
</ul>
<h2 id="readingandwritingexcelfilesinpythonwithpandas">Reading and Writing Excel Files in Python with Pandas</h2>
Naturally, to use Pandas, we first have to install it. The easiest method to install it is via <code>pip</code>.
If you're running Windows:
<pre><code class="hljs">$ python pip install pandas
</code></pre>
If you're using Linux or MacOS:
<pre><code class="hljs">$ pip install pandas
</code></pre>
Note that you may get a <code>ModuleNotFoundError</code> or <code>ImportError</code> error when running the code in this article. For example:
<pre><code class="hljs">ModuleNotFoundError: No module named 'openpyxl'
</code></pre>
If this is the case, then you'll need to install the missing module(s):
<pre><code class="hljs">$ pip install openpyxl xlsxwriter xlrd
</code></pre>
<h2 id="writingexcelfilesusingpandas">Writing Excel Files Using Pandas</h2>
We'll be storing the information we'd like to write to an Excel file in a <code>DataFrame</code>. Using the built-in <code>to_excel()</code> function, we can extract this information into an Excel file.
First, let's import the Pandas module:
<pre><code class="hljs">import pandas as pd
</code></pre>
Now, let's use a <a target="_blank" href="/python-dictionary-tutorial/">dictionary</a> to populate a <code>DataFrame</code>:
<pre><code class="hljs">df = pd.DataFrame({&#x27;States&#x27;:[&#x27;California&#x27;, &#x27;Florida&#x27;, &#x27;Montana&#x27;, &#x27;Colorodo&#x27;, &#x27;Washington&#x27;, &#x27;Virginia&#x27;],
 &#x27;Capitals&#x27;:[&#x27;Sacramento&#x27;, &#x27;Tallahassee&#x27;, &#x27;Helena&#x27;, &#x27;Denver&#x27;, &#x27;Olympia&#x27;, &#x27;Richmond&#x27;],
 &#x27;Population&#x27;:[&#x27;508529&#x27;, &#x27;193551&#x27;, &#x27;32315&#x27;, &#x27;619968&#x27;, &#x27;52555&#x27;, &#x27;227032&#x27;]})
</code></pre>
The keys in our dictionary will serve as column names. Similarly, the values become the rows containing the information.
Now, we can use the <code>to_excel()</code> function to write the contents to a file. The only argument is the file path:
<pre><code class="hljs">df.to_excel(&#x27;./states.xlsx&#x27;)
</code></pre>
Here's the Excel file that was created:
<img src="https://stackabuse.s3.amazonaws.com/media/reading-and-writing-excel-files-python-pandas-library-1.png" alt="states spreadsheet">
Please note that we are not using any parameters in our example. Therefore, the sheet within the file retains its default name - &quot;Sheet 1&quot;. As you can see, our Excel file has an additional column containing numbers. These numbers are the indices for each row, coming straight from the Pandas <code>DataFrame</code>.
We can change the name of our sheet by adding the <code>sheet_name</code> parameter to our <code>to_excel()</code> call:
<pre><code class="hljs">df.to_excel(&#x27;./states.xlsx&#x27;, sheet_name=&#x27;States&#x27;)
</code></pre>
Similarly, adding the <code>index</code> parameter and setting it to <code>False</code> will remove the index column from the output:
<pre><code class="hljs">df.to_excel(&#x27;./states.xlsx&#x27;, sheet_name=&#x27;States&#x27;, index=False)
</code></pre>
Now, the Excel file looks like this:
<img src="https://stackabuse.s3.amazonaws.com/media/reading-and-writing-excel-files-python-pandas-library-2.png" alt="states spreadsheet without index">
<h3 id="writingmultipledataframestoanexcelfile">Writing Multiple DataFrames to an Excel File</h3>
It is also possible to write multiple dataframes to an Excel file. If you'd like to, you can set a different sheet for each dataframe as well:
<pre><code class="hljs">income1 = pd.DataFrame({&#x27;Names&#x27;: [&#x27;Stephen&#x27;, &#x27;Camilla&#x27;, &#x27;Tom&#x27;],
 &#x27;Salary&#x27;:[100000, 70000, 60000]})

income2 = pd.DataFrame({&#x27;Names&#x27;: [&#x27;Pete&#x27;, &#x27;April&#x27;, &#x27;Marty&#x27;],
 &#x27;Salary&#x27;:[120000, 110000, 50000]})

income3 = pd.DataFrame({&#x27;Names&#x27;: [&#x27;Victor&#x27;, &#x27;Victoria&#x27;, &#x27;Jennifer&#x27;],
 &#x27;Salary&#x27;:[75000, 90000, 40000]})

income_sheets = {&#x27;Group1&#x27;: income1, &#x27;Group2&#x27;: income2, &#x27;Group3&#x27;: income3}
writer = pd.ExcelWriter(&#x27;./income.xlsx&#x27;, engine=&#x27;xlsxwriter&#x27;)

for sheet_name in income_sheets.keys():
 income_sheets[sheet_name].to_excel(writer, sheet_name=sheet_name, index=False)

writer.save()
</code></pre>
Here, we've created 3 different dataframes containing various names of employees and their salaries as data. Each of these dataframes is populated by its respective dictionary.
We've combined these three within the <code>income_sheets</code> variable, where each key is the sheet name, and each value is the <code>DataFrame</code> object.
Finally, we've used the <code>xlsxwriter</code> engine to create a <code>writer</code> object. This object is passed to the <code>to_excel()</code> function call.
Before we even write anything, we loop through the keys of <code>income</code> and for each key, write the content to the respective sheet name.
Here is the generated file:
<img src="https://stackabuse.s3.amazonaws.com/media/reading-and-writing-excel-files-python-pandas-library-3.png" alt="multi-sheet excel file">
You can see that the Excel file has three different sheets named <code>Group1</code>, <code>Group2</code>, and <code>Group3</code>. Each of these sheets contains names of employees and their salaries with respect to the date in the three different dataframes in our code.
The engine parameter in the <code>to_excel()</code> function is used to specify which underlying module is used by the Pandas library to create the Excel file. In our case, the <a rel="nofollow noopener" target="_blank" href="https://xlsxwriter.readthedocs.io/index.html"><code>xlsxwriter</code></a> module is used as the engine for the <code>ExcelWriter</code> class. Different engines can be specified depending on their respective features.
Depending upon the Python modules installed on your system, the other options for the engine attribute are: <code>openpyxl</code> (for <code>xlsx</code> and <code>xlsm</code>), and <code>xlwt</code> (for <code>xls</code>).
Further details of using the <code>xlsxwriter</code> module with Pandas library are available at <a rel="nofollow noopener" target="_blank" href="https://xlsxwriter.readthedocs.io/working_with_pandas.html">the official documentation</a>.
Last but not least, in the code above we have to explicitly save the file using <code>writer.save()</code>, otherwise it won't be persisted on the disk.
<h2 id="readingexcelfileswithpandas">Reading Excel Files with Pandas</h2>
In contrast to writing <code>DataFrame</code> objects to an Excel file, we can do the opposite by reading Excel files into <code>DataFrame</code>s. Packing the contents of an Excel file into a <code>DataFrame</code> is as easy as calling the <code>read_excel()</code> function:
<pre><code class="hljs">students_grades = pd.read_excel(&#x27;./grades.xlsx&#x27;)
students_grades.head()
</code></pre>
For this example, we're reading <a rel="nofollow noopener" target="_blank" href="https://stackabuse.s3.amazonaws.com/files/reading-and-writing-excel-files-in-python-with-pandas-grades.xlsx">this Excel file</a>.
Here, the only required argument is the path to the Excel file. The contents are read and packed into a <code>DataFrame</code>, which we can then preview via the <code>head()</code> function.
Note: Using this method, although the simplest one, will only read the first sheet.
Let's take a look at the output of the <code>head()</code> function:
<img src="https://stackabuse.s3.amazonaws.com/media/reading-and-writing-excel-files-python-pandas-library-4.png" alt="grades dataframe">
Pandas assigns a row label or numeric index to the <code>DataFrame</code> by default when we use the <code>read_excel()</code> function.
We can override the default index by passing one of the columns in the Excel file as the <code>index_col</code> parameter:
<pre><code class="hljs">students_grades = pd.read_excel(&#x27;./grades.xlsx&#x27;, sheet_name=&#x27;Grades&#x27;, index_col=&#x27;Grade&#x27;)
students_grades.head()
</code></pre>
Running this code will result in:
<img src="https://stackabuse.s3.amazonaws.com/media/reading-and-writing-excel-files-python-pandas-library-5.png" alt="grades index">
In the example above, we have replaced the default index with the &quot;Grade&quot; column from the Excel file. However, you should only override the default index if you have a column with values that could serve as a better index.
<h3 id="readingspecificcolumnsfromanexcelfile">Reading Specific Columns from an Excel File</h3>
Reading a file in its entirety is useful, though in many cases, you'd really want to access a certain element. For example, you might want to read the element's value and assign it to a field of an object.
Again, this is done using the <code>read_excel()</code> function, though, we'll be passing the <code>usecols</code> parameter. For example, we can limit the function to only read certain columns. Let's add the parameter so that we read the columns that correspond to the &quot;Student Name&quot;, &quot;Grade&quot; and &quot;Marks Obtained&quot; values.
We do this by specifying the numeric index of each column:
<pre><code class="hljs">cols = [0, 1, 3]

students_grades = pd.read_excel(&#x27;./grades.xlsx&#x27;, usecols=cols)
students_grades.head()
</code></pre>
Running this code will yield:
<img src="https://stackabuse.s3.amazonaws.com/media/reading-and-writing-excel-files-python-pandas-library-6.png" alt="dataframe usecols">
As you can see, we are only retrieving the columns specified in the <code>cols</code> list.
<h2 id="conclusion">Conclusion</h2>
We've covered some general usage of the <code>read_excel()</code> and <code>to_excel()</code> functions of the Pandas library. With them, we've read existing Excel files and written our own data to them.
Using various parameters, we can alter the behavior of these functions, allowing us to build customized files, rather than just dumping everything from a <code>DataFrame</code>.

Guest Contributor

In this tutorial, we'll be reading and writing Excel files in Python with Pandas, including examples of using DataFrames and file handling.

Reading and Writing Excel Files in Python with the Pandas Library

Reading and Writing Excel (XLSX) Files in Python with the Pandas Library

<h3 id="introduction">Introduction</h3>
Binary Search is an efficient search algorithm that works on sorted arrays. It's often used as one of the first examples of algorithms that run in logarithmic time (O(logn)) because of its intuitive behavior and is a fundamental algorithm in computer science.
<blockquote>
In this article, we'll be diving into the idea behind and Python implementation of Binary Search.
</blockquote>
<h3 id="binarysearchexample">Binary Search - Example</h3>
Binary Search works on a divide-and-conquer approach and relies on the fact that the array is sorted to eliminate half of possible candidates in each iteration. More specifically, it compares the middle element of the sorted array to the element it's searching for in order to decide where to continue the search.
If the target element is larger than the middle element - it can't be located in the first half of the collection so it's discarded. The same goes the other way around.

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: If the array has an even number of elements, it doesn't matter which of the two &quot;middle&quot; elements we use to begin with.

 </div>
 </div>
 </div>
 Let's look at an example quickly before we continue to explain how binary search works:
<img src="https://stackabuse.s3.amazonaws.com/media/binary-search-in-python-1.png" alt="binary search in python visualization">
As we can see, we know for sure that, since the array is sorted, the element we're looking for (<code>18</code>) is not in the first half of the original array.

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: From now on, we'll mark the element we're looking for as <code>x</code>.

 </div>
 </div>
 </div>
 When we know in which half of the original array <code>x</code> is, we can repeat this exact process with that half and split it into halves again, discarding the half that surely doesn't contain <code>x</code>:
<img src="https://stackabuse.s3.amazonaws.com/media/binary-search-in-python-2.png" alt="binary search in python visualization">
We repeat this process until we end up with a subarray that contains only one element. We check whether that element is <code>x</code>. If it is - we found <code>x</code>, if it isn't - <code>x</code> doesn't exist in the array at all.
If you take a closer look at this, you can notice that in the worst-case scenario (<code>x</code> not existing in the array), we need to check a much smaller number of elements than we'd need to in an unsorted array - which would require something more along the lines of Linear Search, which is insanely inefficient.
To be more precise, the number of elements we need to check in the worst case is O(log2N) where N is the number of elements in the array.
This makes a bigger impact the bigger the array is:
<blockquote>
If our array had 10 elements, we would need to check only 3 elements to either find <code>x</code> or conclude it's not there. That's 33.3%.
However, if our array had 10,000,000 elements we would only need to check 24 elements. That's 0.0002%.
</blockquote>
<h3 id="binarysearchimplementation">Binary Search Implementation</h3>
Binary Search is a naturally recursive algorithm since the same process is repeated on smaller and smaller arrays until an array of size 1 has been found. However, there is of course an iterative implementation as well, and we will be showing both approaches.
<h4 id="recursive">Recursive</h4>
Let's start off with the recursive implementation as it's more natural:
<pre><code class="hljs">def binary_search_recursive(array, element, start, end):
 if start &gt; end:
 return -1

 mid = (start + end) // 2
 if element == array[mid]:
 return mid

 if element &lt; array[mid]:
 return binary_search_recursive(array, element, start, mid-1)
 else:
 return binary_search_recursive(array, element, mid+1, end)
</code></pre>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: This code is simplified to best illustrate the use of the binary serach. It's not fully production-ready, since it lacks proper error handling. Nevertheless, you can use it to implement binary search, just be aware that you wouldn't be able to get appropriate error messages prompted to you.

 </div>
 </div>
 </div>
 Let's take a closer look at this code. We exit the recursion if the <code>start</code> element is higher than the <code>end</code> element:
<pre><code class="hljs">if start &gt; end:
 return -1
</code></pre>
This is because this situation occurs only when the element doesn't exist in the array. What happens is that we end up with only one element in the current sub-array, and that element doesn't match the one we're looking for.
At this point, the <code>start</code> is equal to the <code>end</code>. However, since the <code>element</code> isn't equal to <code>array[mid]</code>, we &quot;split&quot; the array again in such a way that we either decrease <code>end</code> by 1, or increase <code>start</code> by one, and the recursion exists on that condition.
We could have done this using a different approach:
<pre><code class="hljs">if len(array) == 1:
 if element == array[mid]:
 return mid
 else:
 return -1
</code></pre>
The rest of the code does the &quot;check middle element, continue search in the appropriate half of the array&quot; logic. We find the index of the middle element and check whether the element we're searching for matches it:
<pre><code class="hljs">mid = (start + end) // 2
if elem == array[mid]:
 return mid
</code></pre>
If it doesn't, we check whether the element is smaller or larger than the middle element:
<pre><code class="hljs">if element &lt; array[mid]:
 # Continue the search in the left half
 return binary_search_recursive(array, element, start, mid-1)
else:
 # Continue the search in the right half
 return binary_search_recursive(array, element, mid+1, end)
</code></pre>
Let's go ahead and run this algorithm, with a slight modification so that it prints out which subarray it's working on currently:
<pre><code class="hljs">element = 18
array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]

print(&quot;Searching for {}&quot;.format(element))
print(&quot;Index of {}: {}&quot;.format(element, binary_search_recursive(array, element, 0, len(array))))
</code></pre>
Running this code will result in:
<pre><code class="hljs">Searching for 18
Subarray in step 0:[1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 1:[16, 18, 24, 28, 29]
Subarray in step 2:[16, 18]
Subarray in step 3:[18]
Index of 18: 7
</code></pre>
It's clear to see how it halves the search space in each iteration, getting closer and closer to the element we're looking for. If we tried searching for an element that doesn't exist in the array, the output would be:
<pre><code class="hljs">Searching for 20
Subarray in step 0: [4, 14, 16, 17, 19, 21, 24, 28, 30, 35, 36, 38, 39, 40, 41, 43]
Subarray in step 1: [4, 14, 16, 17, 19, 21, 24, 28]
Subarray in step 2: [19, 21, 24, 28]
Subarray in step 3: [19]
Index of 20: -1
</code></pre>
And just for the fun of it, we can try searching some large arrays and seeing how many steps it takes Binary Search to figure out whether a number exists:
<pre><code class="hljs">Searching for 421, in an array with 200 elements
Search finished in 6 steps. Index of 421: 169

Searching for 1800, in an array with 1500 elements
Search finished in 11 steps. Index of 1800: -1

Searching for 3101, in an array with 3000 elements
Search finished in 8 steps. Index of 3101: 1551
</code></pre>
<h4 id="iterative">Iterative</h4>
The iterative approach is very simple and similar to the recursive approach. Here, we just perform the checks in a <code>while</code> loop:
<pre><code class="hljs">def binary_search_iterative(array, element):
 mid = 0
 start = 0
 end = len(array)
 step = 0

 while (start &lt;= end):
 print(&quot;Subarray in step {}: {}&quot;.format(step, str(array[start:end+1])))
 step = step+1
 mid = (start + end) // 2

 if element == array[mid]:
 return mid

 if element &lt; array[mid]:
 end = mid - 1
 else:
 start = mid + 1
 return -1
</code></pre>
Let's populate an array and search for an element within it:
<pre><code class="hljs">element = 18
array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29] 

print(&quot;Searching for {} in {}&quot;.format(element, array))
print(&quot;Index of {}: {}&quot;.format(element, binary_search_iterative(array, element)))
</code></pre>
Running this code gives us the output of:
<pre><code class="hljs">Searching for 18 in [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 0: [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 1: [16, 18, 24, 28, 29]
Subarray in step 2: [16, 18]
Subarray in step 3: [18]
Index of 18: 7
</code></pre>
<h3 id="conclusion">Conclusion</h3>
Binary Search is an incredible algorithm to use on large, sorted arrays, or whenever we plan to search for elements repeatedly in a single array.
The cost of sorting the array once and then using Binary Search to find elements in it multiple times is far better than using Linear Search on an unsorted array just so we could avoid the cost of sorting it.
If we're sorting the array and searching for an element just once, it's more efficient to just do a Linear Search on the unsorted array.
If you'd like to read about <a target="_blank" href="/sorting-algorithms-in-python">Sorting Algorithms in Python</a>, we've got you covered!

Olivera Popović

In this tutorial, we'll be covering Binary Search in Python, its idea, and both the iterative and recursive implementation.

Binary Search in Python

Mina Krivokuća

In this tutorial, we'll be covering how to use grep, as a command-line tool. We'll cover its options as well as practical examples and use cases.

How to Use the grep Command on GNU/Linux

François Dupire

In this tutorial, we'll dive into Relationship Mapping with JPA and Hibernate in Java, with examples of Many-to-Many, One-to-Many, Many-to-One and One-to-One annotations.

Guide to JPA with Hibernate - Relationship Mapping

<h2 id="introduction">Introduction</h2>
In this article, we will explain what the idea behind Insertion Sort is and implement it in JavaScript.
Insertion Sort is one of the simpler sorting algorithms. It's highly intuitive, stable, in-place, and of comparison-type.
A stable sorting algorithm is an algorithm in which two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
In other words, if a sorting algorithm is stable, equivalent elements retain their relative positions after the sorting algorithm is done.
An in-place algorithm is an algorithm that uses no additional memory or data structures, rewriting the original memory locations of the elements in the input array or list.
Finally, a comparison algorithm is the one that, during its execution, only reads list elements through a single abstract comparison operation. Depending on your data type and goal, the comparison can be done via a relational operator or through a custom comparison function.
Despite it having a very large time complexity for a sorting algorithm, Insertion Sort can be very useful, sometimes even being able to outperform some of the most efficient sorting algorithms, such as Quicksort or Merge Sort, on small collections.
It's rarely used as a standalone algorithm - you'd typically use a fast sorting algorithm like Quicksort and finish up the last &quot;loose ends&quot; with Insertion Sort since it's highly efficient for that task.
<h2 id="insertionsort">Insertion Sort</h2>
The idea behind Insertion Sort is often compared to the way people sort a hand of cards while playing Rummy.
In this card game, the dealer deals out cards to each player. Then, the players take the cards given to them one by one, sorting them in their hand in ascending order by inserting each card in its place.
During this entire process, the players hold one sorted pile of cards in their hands, while the unsorted pile from which they draw new cards is in front of them.
A very useful property of Insertion Sort is the fact that it doesn't need to know the entire array in advance in order for it to be sorted - it just inserts the given elements one by one.
This really comes in handy when we want to add more elements in an already sorted array, because Insertion Sort will add the new elements in their proper places without resorting to the entire collection.
Here's a visual representation of how Insertion Sort works:
<img src="https://stackabuse.s3.amazonaws.com/media/insertion-sort-in-java.gif" alt="insertion sort visual representation">
<h2 id="insertionsortimplementation">Insertion Sort Implementation</h2>
Now that we understand the idea behind Insertion Sort, we can move on to the implementation:
<pre><code class="hljs">function insertionSort(inputArr) {
 let n = inputArr.length;
 for (let i = 1; i &lt; n; i++) {
 // Choosing the first element in our unsorted subarray
 let current = inputArr[i];
 // The last element of our sorted subarray
 let j = i-1; 
 while ((j &gt; -1) &amp;&amp; (current &lt; inputArr[j])) {
 inputArr[j+1] = inputArr[j];
 j--;
 }
 inputArr[j+1] = current;
 }
 return inputArr;
}
</code></pre>
The iteration starts at the second element. We consider the first element sorted by default. For each iteration, we keep track of the <code>current</code> element. Each <code>current</code> element will be the first element of the unsorted array - and each element before it will belong to the sorted array.
Through a <code>while</code> loop, we go through the sorted array and shift elements to the right, opening up a space for the <code>current</code> element to be inserted.
Once we find the proper place for it, the <code>current</code> element is inserted into the newly-opened slot. This process is repeated for each iteration until the array is sorted.
Now, let's populate an array and call our sorting algorithm:
<pre><code class="hljs">let inputArr = [5, 2, 4, 6, 1, 3];
insertionSort(inputArr);
console.log(inputArr);
</code></pre>
The output of this array will be:
<pre><code class="hljs">(6) [1, 2, 3, 4, 5, 6]
</code></pre>
Let's go over this example step-by step:
First Iteration:
<blockquote>
Sorted array: 5 
Unsorted array: 2, 4, 6, 1, 3
</blockquote>
<ul>
<li>The first element in our unsorted array is 2.</li>
<li>2 &lt; 5, so we move 5 one place to the right.</li>
</ul>
<blockquote>
Sorted array: _, 5
</blockquote>
<ul>
<li>2 is placed in its right spot.</li>
</ul>
Second Iteration:
<blockquote>
Sorted array: 2, 5 
Unsorted array: 4, 6, 1, 3
</blockquote>
<ul>
<li>The first element in our unsorted array is 4.</li>
<li>4 &lt; 5, so we move 5 one place to the right.</li>
</ul>
<blockquote>
Sorted array: 2, _, 5
</blockquote>
<ul>
<li>4 !&lt; 2, so we don't move 2.</li>
<li>4 is placed in its right spot.</li>
</ul>
Third Iteration:
<blockquote>
Sorted array: 2, 4, 5 
Unsorted array: 6, 1, 3
</blockquote>
<ul>
<li>The first element in our unsorted array is 6.</li>
<li>6 !&lt; 5, so we don't move 5.</li>
</ul>
<blockquote>
Sorted array: 2, 4, 5
</blockquote>
<ul>
<li>6 is placed in its right spot.</li>
</ul>
This is repeated until we're greeted with a sorted array: <code>1, 2, 3, 4, 5, 6</code>.
We can notice an invariant in each of these iterations. For the <code>k-th</code> iteration of our loop, the interval of <code>[0,k]</code> is guaranteed to be sorted.
<h2 id="timecomparison">Time Comparison</h2>
The best running time of Insertion Sort is linear, and we get it if our input array is already sorted. This means that Insertion Sort works wonders when it comes to checking whether or not the array is sorted.
However, the worst and average time complexity is O(n2), which is pretty bad for a sorting algorithm, especially when it is applied to arrays or lists of a bigger size. In this case, Quicksort or Merge Sort with a complexity of O(nlogn) would be a much better choice.
On the other hand, being one of the fastest quadratic sorting algorithms, Insertion Sort usually outperforms <a target="_blank" href="/bubble-sort-and-cocktail-shaker-sort-in-javascript/">Bubble Sort</a>, Gnome Sort and <a target="_blank" href="/selection-sort-in-javascript/">Selection Sort</a>. In addition to that, when our input array size is very small (10-20 elements), Insertion Sort can even outperform Quicksort and Merge Sort.
This is why JavaScript, despite using Quicksort (in Chrome) or Merge Sort (in Mozilla) as the primary sorting algorithm, also uses Insertion Sort on small collections - and after Quicksort/Merge Sort has done the bulk of the work.
<h2 id="conclusion">Conclusion</h2>
Insertion Sort is a simple, stable, in-place, comparison sorting algorithm.
Despite being pretty time-consuming with quadratic complexity, it is very useful when the input array is small in size. In this case, it even outperforms the most commonly used divide-and-conquer algorithms, which is why JavaScript uses a combination of Insertion Sort and Merge Sort or Quicksort when using built-in sorting functions.
When it comes to larger-sized arrays, it outperforms most other quadratic sorting algorithms, including Bubble Sort, Gnome Sort, as well as Selection Sort.

Mila Lukic

In this tutorial, we'll be explaining and implementing Insertion Sort in JavaScript, analyzing its Time Complexity, and comparing it to other algorithms.

Insertion Sort in JavaScript

<h2 id="introduction">Introduction</h2>
In this article, we'll be diving into the Factory Method Design Pattern, implemented in Python.
Design Patterns define tried and tested solutions to various recurring problems in software development. They do not represent actual code, but rather ways in which we can organize our code for the optimum results.
In a world of limited resources, Design Patterns help us achieve the most results with the least amount of used resources. It is also important to note that Design Patterns do not apply to all situations and it is crucial to assess the problem at hand in order to choose the best approach for that particular scenario.
Design Patterns are divided into a few broad categories, though mainly into Creational Patterns, Structural Patterns, and Behavioral Patterns.
The Factory Method pattern is a Creational Design Pattern.
<h2 id="thefactorymethoddesignpattern">The Factory Method Design Pattern</h2>
<h3 id="definition">Definition</h3>
The Factory Method is used in object-oriented programming as a means to provide factory interfaces for creating objects. These interfaces define the generic structure, but don't initialize objects. The initialization is left to more specific subclasses.
The parent class/interface houses all the standard and generic behavior that can be shared across subclasses of different types. The subclass is in turn responsible for the definition and instantiation of the object based on the superclass.
<h3 id="motivation">Motivation</h3>
The main motivation behind the Factory Method Design Pattern is to enhance loose coupling in code through the creation of an abstract class that will be used to create different types of objects that share some common attributes and functionality.
This results in increased flexibility and reuse of code because the shared functionality will not be rewritten having been inherited from the same class. This design pattern is also known as a Virtual Constructor.
The Factory Method design pattern is commonly used in libraries by allowing clients to choose what subclass or type of object to create through an abstract class.
A Factory Method will receive information about a required object, instantiate it and return the object of the specified type. This gives our application or library a single point of interaction with other programs or pieces of code, thereby encapsulating our object creation functionality.
<h3 id="factorymethodimplementation">Factory Method Implementation</h3>
Our program is going to be a library used for handling shape objects in terms of creation and other operations such as adding color and calculating the area of the shape.
Users should be able to use our library to create new objects. We can start by creating single individual shapes and availing them as is but that would mean that a lot of shared logic will have to be rewritten for each and every shape we have available.
The first step to solving this repetition would be to create a parent shape class that has methods such as <code>calculate_area()</code> and <code>calculate_perimeter()</code>, and properties such as dimensions.
The specific shape objects will then inherit from our base class. To create a shape, we will need to identify what kind of shape is required and create the subclass for it.
We will start by creating an abstract class to represent a generic shape:
<pre><code class="hljs">import abc
class Shape(metaclass=abc.ABCMeta):
 @abc.abstractmethod
 def calculate_area(self):
 pass

 @abc.abstractmethod
 def calculate_perimeter(self):
 pass
</code></pre>
This is the base class for all of our shapes. Let's go ahead and create several concrete, more specific shapes:
<pre><code class="hljs">class Rectangle(Shape):
 def __init__(self, height, width):
 self.height = height
 self.width = width

 def calculate_area(self):
 return self.height * self.width 

 def calculate_perimeter(self):
 return 2 * (self.height + self.width) 

class Square(Shape):
 def __init__(self, width):
 self.width = width

 def calculate_area(self):
 return self.width ** 2

 def calculate_perimeter(self):
 return 4 * self.width

class Circle(Shape):
 def __init__(self, radius):
 self.radius = radius

 def calculate_area(self):
 return 3.14 * self.radius * self.radius

 def calculate_perimeter(self):
 return 2 * 3.14 * self.radius
</code></pre>
So far, we have created an abstract class and extended it to suit different shapes that will be available in our library. In order to create the different shape objects, clients will have to know the names and details of our shapes and separately perform the creation.
This is where the Factory Method comes into play.
The Factory Method design pattern will help us abstract the available shapes from the client, i.e. the client does not have to know all the shapes available, but rather only create what they need during runtime. It will also allow us to centralize and encapsulate the object creation.
Let us achieve this by creating a <code>ShapeFactory</code> that will be used to create the specific shape classes based on the client's input:
<pre><code class="hljs">class ShapeFactory:
 def create_shape(self, name):
 if name == &#x27;circle&#x27;:
 radius = input(&quot;Enter the radius of the circle: &quot;)
 return Circle(float(radius))

 elif name == &#x27;rectangle&#x27;:
 height = input(&quot;Enter the height of the rectangle: &quot;)
 width = input(&quot;Enter the width of the rectangle: &quot;)
 return Rectangle(int(height), int(width))

 elif name == &#x27;square&#x27;:
 width = input(&quot;Enter the width of the square: &quot;)
 return Square(int(width))
</code></pre>
This is our interface for creation. We don't call the constructors of concrete classes, we call the Factory and ask it to create a shape.
Our <code>ShapeFactory</code> works by receiving information about a shape such as a name and the required dimensions. Our factory method <code>create_shape()</code> will then be used to create and return ready objects of the desired shapes.
The client doesn't have to know anything about the object creation or specifics. Using the factory object, they can create objects with minimal knowledge of how they work:
<pre><code class="hljs">def shapes_client():
 shape_factory = ShapeFactory()
 shape_name = input(&quot;Enter the name of the shape: &quot;)

 shape = shape_factory.create_shape(shape_name)

 print(f&quot;The type of object created: {type(shape)}&quot;)
 print(f&quot;The area of the {shape_name} is: {shape.calculate_area()}&quot;)
 print(f&quot;The perimeter of the {shape_name} is: {shape.calculate_perimeter()}&quot;)
</code></pre>
Running this code will result in:
<pre><code class="hljs">Enter the name of the shape: circle
Enter the radius of the circle: 7

The type of object created: &lt;class &#x27;__main__.Circle&#x27;&gt;
The area of the circle is: 153.86
The perimeter of the circle is: 43.96
</code></pre>
Or, we could build another shape:
<pre><code class="hljs">Enter the name of the shape: square
Enter the width of the square: 5

The type of object created: &lt;class &#x27;__main__.Square&#x27;&gt;
The area of the square is: 25
The perimeter of the square is: 20
</code></pre>
What's worth noting is that besides the client not having to know much about the creation process - when we'd like to instantiate an object, we don't call the constructor of the class. We ask the factory to do this for us based on the info we pass to the <code>create_shape()</code> function.
<h2 id="prosandcons">Pros and Cons</h2>
<h3 id="pros">Pros</h3>
One of the major advantages of using the Factory Method design pattern is that our code becomes loosely coupled in that the majority of the components of our code are unaware of other components of the same codebase.
This results in code that is easy to understand and test and adds more functionality to specific components without affecting or breaking the entire program.
The Factory Method design pattern also helps uphold the Single Responsibility Principle where classes and objects that handle specific functionality result in better code.
<h3 id="cons">Cons</h3>
Creation of more classes eventually leads to less readability. If combined with an Abstract Factory (factory of factories), the code will soon become verbose, though, maintainable.
<h2 id="conclusion">Conclusion</h2>
In conclusion, the Factory Method Design Pattern allows us to create objects without specifying the exact class required to create the particular object. This allows us to decouple our code and enhances its reusability.
It is important to note that, just like any other design pattern, it is only suitable for specific situations and not every development scenario. An assessment of the situation at hand is crucial before deciding to implement the Factory Method Design Pattern to reap the benefits of the pattern.

Robley Gori

In this tutorial, we'll go through an example and implementation of the Factory Method Design Pattern in Python, alongside the motivation and definition.

The Factory Method Design Pattern in Python

Victoria Seniuk

In this tutorial, we'll implement the Data Transfer Object Pattern in a Java Spring Boot application. We'll also cover examples of mapping entities to DTOs.