In my second article on Medium, I wanna talk about binary search and how this algorithm works on TypeScript. I published my code snippet on this Github repository.

What is a binary search?

Binary search, also known as logarithmic search, is a search algorithm that finds the position of a target value within a data structure (e.g. Array). To accomplish that, the data structure must be sorted. It’s not possible to use a binary search algorithm on an unsorted data structure.

Time Complexity

Worst case: O(log n)
Average case: O(log n)
Best case: O(1)

TypeScript Function

As you can see, the method itself isn’t that complex. But let me explain what is going to happen by an example.

This function binarySearch takes two arguments, an integer array, and an integer.

nums: [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
target: 2

That means, that we want to find the index of that array (NUMS) in which element contains the integer 2 (TARGET).

In a linear search, we would iterate through that array, most likely starting from index 0 until we have found the right element. In a binary search, we repeatedly divide the search interval in half. For that, we follow this flow:

1. Compare TARGET with the mid element.
2. If TARGET matches with the mid element, we return the mid index.
3. Else if TARGET is greater than the mid element, then TARGET can only lie in the right half subarray after the mid element. So we recur for the right half.
4. Else (TARGET is smaller) recur for the left half.

If you wanna more about this search algorithm, then I can recommend you the video from HackerRank.

Thanks for reading my second article on Medium. I hope I could refresh your knowledge.

Cheers!

Use any component in all your projects

Up until now, you used to build features hidden inside larger projects.

But what if you were to develop independent features first, and then easily compose and manage them in many applications? Your development will become faster, more consistent, and more scalable every day. Create a component once, and truly use it anywhere to build anything.

OSS Tools like Bit offer a powerful developer experience for building independent components and composing them to applications. You can start small with a nice project, some shared components, or even trying out Micro Frontends. Give it a try →