DEV Community

Cover image for Binary Search in other words
haytam_7
haytam_7

Posted on

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!

Top comments (0)