Представьте, что вы держите фонарик над списком отсортированных чисел в поисках вашего лотерейного номера.
Каждый раз, когда вы включаете фонарик, он автоматически указывает на середину списка и ты не можешь этого изменить. Если в этот момент вы увидите свой лотерейный номер, тогда БУМ! ты выиграл в лотерею.
В противном случае вам нужно сравнить свой лотерейный номер с тем номером в середине списка, и вы столкнетесь с одной из двух ситуаций:
Либо ваш номер больше, тогда вам придется вырезать нижнюю часть списка и продолжить работу с верхней частью.
Или ваш номер меньше, чем вам нужно, чтобы сократить верхнюю часть списка и продолжить работу с нижней частью.
Теперь давайте попробуем перевести это в код (на 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;
}
Самое замечательное в этом алгоритме то, что на каждой итерации вы сокращаете половину списка и в худшем случае это будет стоить вам O (Log n) временной сложности и O(1) пространственной сложности!
Оригинал: “https://dev.to/haytamkh7/binary-search-in-other-words-1n0e”