Объяснение алгоритма поиска!
Двоичный поиск — это алгоритм поиска, используемый для поиска определенного элемента в отсортированном массиве.
В чем его особенность?
Алгоритм разработан таким образом, что с каждой итерацией размер задачи уменьшается вдвое.
Прохладный. Разве это не так? Без дальнейших церемоний, давайте погрузимся в семантику.
Почему бинарный поиск?
У нас есть линейный поиск, в котором вам нужно перебирать каждый элемент и проверять, соответствует ли он нужному элементу. Вы получите свой ответ просто отлично. Но что плохого в этом подходе?
Это то, что мы называем сложностью времени. Временная сложность — это математическая функция, которая коррелирует с ростом времени по мере увеличения размера входных данных.
ПРИМЕЧАНИЕ. Это время зависит только от размера входных данных, а не от машины или компилятора.
При линейном поиске по мере роста размера входных данных, в нашем случае массива, время, затрачиваемое на поиск, также увеличивается линейно, потому что нам приходится перебирать каждый элемент массива. По этой причине временная сложность линейного поиска в наихудшем случае оказывается равной O(n)(Linear), где n — размер массива. Если размер равен 10 000, время также линейно увеличилось бы в 10 000 раз.
Для оптимизации поиска больших наборов данных был разработан Binary Search.
Вы берете массив и хотите найти, существует ли элемент в массиве. Итак, прежде чем применять алгоритм, вы сортируете массив в порядке возрастания (по убыванию тоже работает, но вам нужно добавить больше кода) и применяете алгоритм.
Как он ищет?
Вы используете метод двух указателей (начало и конец), назначаете их первой и последней позициям в массиве. Далее идет цикл с условием «начало ≤ конец», и вы находите средний элемент, используя эту формулу:
начало + (конец-начало)/2.
Вы можете использовать простое (начало+конец)/2, но если значения очень высоки, деление может выйти за границы.
По этой причине вы сортируете массив перед применением поиска. Вам нужно получить медианное значение конкретного набора данных. Если не сортировать, то нет смысла даже искать средний элемент.
После получения среднего элемента в массиве вы используете простые операторы if-else и проверяете три случая:
- Если целевой элемент ‹ элемент в середине:
если правда, вы можете сдвинуть значение конечного указателя и изменить его на end = middle -1
2. если целевой элемент › элемент посередине:
если true, вы можете сдвинуть значение начального указателя и изменить его на start = middle+1
3. если цель == элемент посередине.
Если это правда, отлично, это ваш ответ.
Если ни одно из этих условий не выполняется, это указывает на то, что требуемый элемент не существует в массиве, и возвращает значение по умолчанию.
Если вы заметите, что в первых двух случаях, если любой из них окажется верным, вы уменьшите размер проблемы в два раза. Если размер вашего массива равен 10 000, после проверки условия это будет половина. Поэтому мы также называем этот алгоритм «Разделяй и властвуй».
Временная сложность бинарного поиска в наихудшем случае составляет O(Log n), потому что для каждой итерации мы уменьшаем размер задачи на 2.
Код для бинарного поиска:
public class BinarySearch {
static int BinSearch(int[] arr, int target){
int start = 0;
int end = arr.length-1;
while(start <= end) {
int mid = start + (end-start)/2;
if(target < arr[mid]){
end = mid - 1;
}else if(target > arr[mid]){
start = mid + 1;
}else{
return mid;
}
}
return -1; //if element doesn't exist
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9,10}; //already sorted array
int target = 4; //search element
int ans = BinSearch(arr,target);
System.out.println(ans);
}
}
Вы можете применить простой алгоритм сортировки для сортировки массива и применения двоичного поиска.
А пока удачного кодирования!
