This content originally appeared on DEV Community and was authored by haytam_7
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!
This content originally appeared on DEV Community and was authored by haytam_7
haytam_7 | Sciencx (2021-09-30T18:28:22+00:00) Binary Search in other words. Retrieved from https://www.scien.cx/2021/09/30/binary-search-in-other-words/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.