Предположим, у нас есть следующий массив, отсортированный в порядке возрастания.

Предположим, нам нужно найти 29 в приведенном выше массиве. Один из способов найти 29 — проверить каждый элемент из первого индекса, пока мы не найдем 29. Этот линейный поиск занимает O(n) временную сложность.

На самом деле мы можем искать 29 за меньшее время, используя алгоритм бинарного поиска.

Посмотрим, как это работает.

  1. Определите первый индекс как левый, а последний индекс как правый. Затем найдите середину первого и последнего индекса.
  2. Если средняя точка равна искомому числу (цель), возвращаем среднюю точку и останавливаем поиск.
  3. Если цель больше, чем средняя точка, поиск осуществляется только справа от средней точки. Итак, обновите значение left как midpoint + 1.
  4. Если цель меньше, чем средняя точка, ищите только слева от средней точки. Итак, обновите значение right как midpoint — 1.
  5. Повторяйте шаги с 1 по 4, пока элемент слева не станет меньше элемента справа.

Давайте посмотрим на это на примере:

Определите первый индекс как левый, а последний индекс как правый.

Найдите середину первого и последнего индекса. [(первый индекс + последний индекс) / 2]

Проверьте, является ли элемент в середине нашей целью.

Поскольку середина меньше цели, это означает, что цель находится справа от середины. Итак, нам нужно проверить только правую сторону середины.

Итак, обновите значение left как mid + 1.

Снова найти середину.

Проверьте, является ли элемент в середине нашей целью.

Поскольку середина больше цели, это означает, что цель находится слева от середины. Итак, нам нужно проверить только левую часть середины.

Итак, обновите значение right как mid — 1.

Снова найти середину.

Поскольку mid равно target, остановите поиск.

Целевое значение соответствует индексу 5.

Сложность времени: O(logn)

Код

public class SearchElement {
public int search(int[] nums, int target) {
int mid = (0 + nums.length - 1) / 2;
int index = -1;
  if (target == nums[mid]) {
   index = mid;
  }
else if (target > nums[mid]) {
for (int i = mid + 1; i < nums.length; i++) {
    if (target == nums[i]) {
     index = i;    }
   }
  } else {
   for (int i = 0; i < mid + 1; i++) {
    if (target == nums[i]) {
     index = i;
    }
   }
}
  return index;
}
public static void main(String[] args) {
SearchElement obj = new SearchElement();
  int arr[] = { -1, 0, 3, 5, 9, 12 };
  int index = obj.search(arr, 9);
  System.out.println(index);
 }
}