DEV Community

Cover image for LeetCode Meditations — Chapter 5: Binary Search
Eda
Eda

Posted on • Edited on • Originally published at rivea0.github.io

1

LeetCode Meditations — Chapter 5: Binary Search

Binary search is one of the most well-known algorithms. It's also a divide-and-conquer algorithm, where we break the problem into smaller components.

The crux of binary search is to find a target element in a given sorted array.
We have two pointers: high to point to the largest element, and low to point to the smallest element. We first initialize them for the whole array itself, with high being the last index and low being the first index. Then, we calculate the midpoint. If the target is greater than the midpoint, then we adjust our low pointer to point to the mid + 1, otherwise if the target is less than the midpoint, we adjust high to be mid - 1. With each iteration, we eliminate half the array until the midpoint equals target or the low pointer passes high.

If we find the index of the target, we can return it as soon as we find it; otherwise, we can just return -1 to indicate that the target doesn't exist in the array.

For example, if we have a nums array [-1, 0, 3, 5, 9, 12] and our target is 9, the operation looks like this:

Binary search example

We can write it in TypeScript like this:

function search(nums: number[], target: number): number {
  let high = nums.length - 1;
  let low = 0;

  while (high >= low) {
    let mid = Math.floor((high + low) / 2);

    if (target > nums[mid]) {
      low = mid + 1;
    } else if (target < nums[mid]) {
      high = mid - 1;
    } else {
      return mid;
    }
  }

  return -1;
};
Enter fullscreen mode Exit fullscreen mode
Time and space complexity

The time complexity of a binary search algorithm is O(log n)O(log \ n) in the worst case. (For example, if the target is not in the array, we'll be halving the array until there is one element left.) The space complexity is O(1)O(1) as we don't need extra space.


The first problem in this chapter will be Find Minimum in Rotated Sorted Array, until then, happy coding.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay