В чем заключается суть бинарного поиска неотсортированного массива?

Question

[MishaXXL]

Вводные данные, поиск на наличие числа в массиве
https://leetcode.com/problems/search-in-rotated-so...

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Мне казалось, что бинарный поиск имеет смысл только в отсортированном массиве.
В чем заключается нюанс бинарного поиска неотсортированного массива?

Comments

[WbICHA]

А ты условия задачи вообще читал? К тебе приходит как раз отсортированный массив. Да, со смещением, но он отсортирован.

Answer 1

[Wataru]

Ну ведь тут массив же отсортирован. Хоть и с приколом: он сдвинут. Можно тем же бинарным поиском найти, где там "разрыв" происходит, а после у вас 2 отсортированных куска. Или сразу модифицировать бинпоиск.
Представьте, что у вас массив, где сначала идут 1, а потом 0. Можете найти в нем, где 1 переходит в 0?

Или смотрите так: ищите вы x. Взяли значение a[m]. Можете, посмотрев на a[l], a[m], a[r] и x понять, в какой половине лежит x?

Edit: ах, тут числа могут быть одинаковыми. Тогда бинпоиск тут не работает. Ибо может быть тест {1,1,1,2,1,1} - и тут можно 2 в любую позицию поставить. И, если вам надо эту 2 найти, то вам придется просмотреть все числа, иначе вы ее не найдете. Бинпоиск возможен, если первое и последнее числа разные.

Comments

[vadimr]

Ну то что бинпоиск неэффективен на конкретном примере, не значит, что он не работает в такой задаче вообще.

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

[MishaXXL]

vadimr, пример решения?

[vadimr]

(define a (vector 7 9 1 1 1 2 2 4 5 6))
(define x 4)

(define (1+ x) (+ 1 x))

(define (phase1 l r)
  (let ((m (floor (/ (+ l r) 2))))
    (cond
        ((= (vector-ref a m) x))
        ((>= l r) #f)
        (else (or
            (if (< (vector-ref a l) (vector-ref a m)) 
              (phase2 l m) (phase1 l m))
            (if (< (vector-ref a m) (vector-ref a r)) 
              (phase2 (1+ m) r) (phase1 (1+ m) r))
        ))
    )
  )
)

(define (phase2 l r)
  (let ((m (floor (/ (+ l r) 2))))
    (cond
        ((= (vector-ref a m) x))
        ((>= l r) #f)
        ((> (vector-ref a m) x) (phase2 l m))
        (else (phase2 (1+ m) r))
    )
  )
)

(pp (phase1 0 (- (vector-length a) 1)))

Сложность этого алгоритма логарифмическая от количества уникальных элементов массива плюс линейная от количества повторяющихся, и это значительно лучше того, что пишут индусы на leetcode, начинающие с поиска границы перебором.