Forem: Elias Juremalm

Binary search and big O notation

Elias Juremalm — Tue, 07 Dec 2021 07:23:05 +0000

In this article, I will teach you about big O notation and we will also implement binary search in Python3.

Big O notation

Big O notation is a special notation that tells you how fast your algorithm is. Why does big O notation matter? When you use people's algorithms, it's nice to understand how fast or slow they are. When it comes to measuring algorithms it's not enough to measure the time in seconds because when an algorithm is working with small amounts of operations it can be hard to see a difference. But the more operations you will need to compute, the more time will scale. With big O notation, you can quickly see how much the algorithm will scale based on input. The amount of input into the algorithm is called n.

For example, O(n) will scale linearly while O(n^2) will scale exponentially.

Some common big O notations you will see are the following:

O(1) static.
O(log n), also known as log time. Example: Binary search.
O(n), also known as linear time. Example: Simple search.
O(n * log n). Example: A fast sorting algorithm.
O(n^2). Example: A slow sorting algorithm.
O(n!). Example: A super slow algorithm, like the traveling salesperson problem.

Binary Search

When you need to search for something you'll probably use some kind of algorithm. One popular algorithm is binary search. One of the reasons because it's so popular is its efficiency(O(log n)). Now how does binary search work?

Imagine a sorted list of numbers.
[1, 4, 6, 7, 9, 21, 43]
If I would like to see if number 6 is inside this list and where it is located I could go through each element in the list until I find the number 6. That's simple search. The problem with simple search is that with large lists it will be slow. If I would instead use binary search we could search the list fast even with a large list.

How binary search starts is as the following. Start looking at the number seven. If the number we are looking for is lower we move forward and only look at the left side of the list. If it's higher we only look on the right side. In this case, 6 is lower than 7 so we will look at the left side. Now the numbers we care about are these.
[1, 4, 6]

Now we do the same thing we did before. We start to look at 4, is 6 higher or lower? Higher. We therefore move forward and our list only looks like this:
[6]

Now when we do the same thing again, we'll see that the item we are looking at is the number we are searching for. Boom, we found it! Now if instead, the number we were looking for was 5, we would not have found anything, then our program would return -1 instead.

To sum it up

Look at the item in the middle(lowest value:highest value) of the list
If the list is empty return -1
Check if the item is the one you're looking for.
If yes return index
Check if the item is lower or higher than what you're looking for
Modify list/lowest and highest value
Start over

Now let's implement this in code

Binary search in Python 3

def bin_search(item, arr):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == item:
            return mid

        if arr[mid] < item:
            low = mid + 1
        elif arr[mid] > item:
            high = mid - 1
     return -1

my_list= [1, 4, 6, 7, 9, 21, 43]

print(bin_search(6, my_list)) // Returns 2
print(bin_search(5, my_list)) // Returns -1

The code above is a simple implementation of binary search, there are different ways to implement a binary search and this is one of them. This program will go through the list to search for the item we are looking for.

Recap

Algorithms speed is not measured in seconds.
Algorithm times are written in big O notation.
Big O notation is showing in terms of the growth of an algorithm.
Some common Big O notations: O(n), O(log n), O(n^2), O(n * log n)
Binary search is a fast searching algorithm. Much faster than simple search.

Thank you for reading this short post about Big O notation and Binary Search. This post is part of a data structures and algorithms series I'm working on so make sure to leave a follow if you're interested to see more.

How to get started with vim(neovim) for web development in 2021

Elias Juremalm — Sun, 28 Nov 2021 21:30:31 +0000

Getting started with vim can be feeling hard if all you've seen of vim is a scary old terminal editor. But fear not! When setting up your vim for success with the right plugins and color theme it will become your new best friend.

A quick note I use neovim as my "vim" editor and therefore I will show you the workflow with neovim in this article.

What is VIM?

"Vim is a highly configurable text editor built to make creating and changing any kind of text very efficient. It is included as "vi" with most UNIX systems and with Apple OS X." taken from vim.org.

Now okay, that sounds awesome but why is it very efficient? Vim can be very efficient because of its smallness and simplicity, therefore it does not consume a significant amount of system resources as opposed to other editors.

What is Neovim?

Neovim is a continuation and extension of Vim. Neovim comes with the good parts of vim and more. Neovim has some architectural changes that bring more stability, performance and make the code more maintainable.

Installing Neovim

Neovim got a great wiki section regarding installing it that you can find here

How to install and use vim-plug for neovim.

The plugin manager I use for vim is vim-plug and therefore I will show you how to install that. There are more plugin managers you could use if you want to and feel free to find the one that suits your needs best.

Installing vim-plug for macOS/Linux

Run the following command inside your terminal.

sh -c 'curl -fLo "${XDG_DATA_HOME:-$HOME/.local/share}"/nvim/site/autoload/plug.vim --create-dirs \
 https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim'

Installing vim-plug for Windows

Run the following command inside PowerShell.

iwr -useb https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim |`
    ni "$(@($env:XDG_DATA_HOME, $env:LOCALAPPDATA)[$null -eq $env:XDG_DATA_HOME])/nvim-data/site/autoload/plug.vim" -Force

How to use vim-plug

If you want to learn more on how to use vim-plug you can check out their tutorial

The basics of using vim-plug are:

Begin the section with call plug#begin()
List the plugins with Plug commands
call plug#end() to update &runtimepath and initialize plugin system
- Automatically executes filetype plugin indent on and syntax enable. You can revert the settings after the call. e.g. filetype indent off, syntax off, etc.
Reload ~/config/nvim/init.vim and :PlugInstall to install plugins.

You can reload your init.vim while still editing it by running :so %

Selecting a color theme for neovim.

Now that we got vim-plug installed we can get some colors 🎨

I will show you how to install gruvbox but here you can research and find a color scheme that suits you the best. Installing will be the same for most color schemes.

Inside the vim config add Plug 'morhetz/gruvbox' reload your config and run :PlugInstall

After that, you need to add the following to your vim config. Beware that this does not have to be inside your plug section.

syntax enable
colors gruvbox

An example of how it could look inside your config 👇

call plug#begin()
Plug 'morhetz/gruvbox'
call plug#end()

syntax enable
colors gruvbox

Plugins to improve your developer experience

Some plugins I use daily to improve my developer experience is the following:

Plug 'nvim-telescope/telescope.nvim'
Plug 'scrooloose/nerdtree'
Plug 'itchyny/lightline.vim'

Telescope
Telescope is a highly extendable fuzzy finder over lists.

The following let's you use telescope with the bindings of leader key then ff, fg, fb, fh.

nnoremap <leader>ff <cmd>Telescope find_files<cr>
nnoremap <leader>fg <cmd>Telescope live_grep<cr>
nnoremap <leader>fb <cmd>Telescope buffers<cr>
nnoremap <leader>fh <cmd>Telescope help_tags<cr>

Nerdtree
Nerdtree is a file system explorer.

To toggle Nerdtree add the follwing to your config:
nnoremap <C-Space> :NERDTreeToggle<CR>
This lets your toggle nerdtree with CTRL + Space

Lightline
Lightline is a light and configurable statusline/tabline plugin for Vim

An example of lightline:

Plugins for web development

When working with web development it's nice to have the correct syntax highlighting, autocompletion and linting. I will now show the plugins I use when working with web development(Typescript, Next.js, React, etc.).

Plug 'neoclide/coc.nvim', {'branch': 'release'}

Plug 'maxmellon/vim-jsx-pretty'
Plug 'pangloss/vim-javascript'
Plug 'leafgarland/typescript-vim'
Plug 'peitalin/vim-jsx-typescript'

Plug 'styled-components/vim-styled-components', { 'branch': 'main' }
Plug 'jparise/vim-graphql'

The first plugin I use is coc. Coc is a intellisense engine for VIM. Now the rest plugins I use are providing me with the correct syntax highlighting and autocompletion.

Improving the power of coc

Some extra small tips I have inside my config for coc is the following:

let g:coc_global_extensions = [
  \ 'coc-tsserver'
  \ ]

if isdirectory('./node_modules') && isdirectory('./node_modules/prettier')
  let g:coc_global_extensions += ['coc-prettier']
endif

if isdirectory('./node_modules') && isdirectory('./node_modules/eslint')
  let g:coc_global_extensions += ['coc-eslint']
endif

These make sure that coc with typescript is up to date and installed. Also, since I often use eslint and prettier in my projects I have configured coc to install the relevant coc extension for them if they're being used.

Thank you for reading this blog post! You can find more posts like this on my website: pluppen.com

And at last, don't forget to share your VIM config with me and show off your awesome vim environment.