DEV Community

Cover image for Binary Search in other words
haytam_7
haytam_7

Posted on

3 2

Binary Search in other words

Imagine yourself holding a flashlight against a list of sorted numbers searching for your lottery number.

Each time you turn on the flashlight it will automatically point to the middle of the list and you can't change it.
If at this point you see your lottery number then BOOM! you won the lottery.

Otherwise you need to compare your lottery number with that number in the middle of the list and you will face one of two situations:

Either your number is bigger, then you have to cut the lower part of the list and continue working with the upper part.

Or your number is smaller, then you have to cut the upper part of the list and continue working with the lower part.

Now let's try to translate this to a code (in Java):

public static int myLotteryNumber(int[] list, int lotteryNumber) {
        int left = 0;
        int right = list.length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(list[mid] == lotteryNumber)
                return list[mid];
            else if(lotteryNumber > list[mid])
                left = mid + 1; //cut the lower part of the list
            else if(lotteryNumber < list[mid])
                right = mid - 1; //cut the upper part of the list
        }
        return -1;
    }
Enter fullscreen mode Exit fullscreen mode

The great thing about this algorithm is that at each iteration you cut down half of the list and at the worst case this will cost you O(Log n) of time complexity and O(1) of space complexity!

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more

Top comments (0)