## DEV Community is a community of 787,688 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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;
}
``````

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!