33. Search in Rotated Sorted Array(бинарный поиск).txt

//Нужно реализовать бинарный поиск в отсортированном массиве, который сдвинут на k элементов, за время O(log n).

//Оптимизированный код(Крутое решение)
//Например наши массив = { 4,5,6,7,0,1,2 } где 0 -точка разрыва. Массив смещён на 4 элемента.
//Сначала ищем минимальное значение массива чтобы понять где происходит разрыв. (точка сдвига, вращения). Запоминаем его (rot).
//Мы представляем что массив на самом деле без разрыва:{ 4,5,6,7,0,1,2|,4,5,6,7 } и выполняем двоичный поиск в отсортированном массиве {0, 1, 2, 4, 5, 6, 7}
//относительно новой вооброжаемой серидины.
Массив был:	  4 5 6 7 0 1 2
Мы представляем:  4 5 6 7 0 1 2 4 5 6 7
Его индексы:      0 1 2 3 4 5 6 7
Новые индексы:		  0 1 2 3 4 5 6		
Настоящая середина в этом более длинном массиве — это средняя точка между точкой вращения (rot)и последним элементом: (rot + (hi+rot)) / 2.
(hi + rot) — индекс последнего элемента.(В вооброжаемом массиве) И конечно, этот результат больше реальной середины. 
Так что вам просто нужно завернуть и получить остаток: ((rot + (hi + rot)) / 2) % n. 
И это выражение фактически равно (rot + hi/2) % n, что равно (rot+mid) % n.
% n нужен для получения реального индекса а не вооброжаемого. % мы закругляем массив.


int search(vector<int>& nums, int target) {
	int lo = 0, hi = nums.size() - 1;
	// Находим индекс наименьшего значения с помощью двоичного поиска.
	// Цикл завершится, так как mid < hi, а lo или hi уменьшится хотя бы на 1.
	// Доказательство противоречия, что mid < hi: если mid==hi, то lo==hi и цикл бы завершился.
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (nums[mid] > nums[hi]) lo = mid + 1;
		else hi = mid;
	}
	// lo==hi это индекс наименьшего значения, а также количество мест поворота.
	int rot = lo;//На сколько смещён массив.
	lo = 0; hi = nums.size() - 1;
	// Обычный двоичный поиск и учет поворота.
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		int realmid = (mid + rot) % nums.size(); // % делает массив похожим на круг.
		if (nums[realmid] == target)return realmid;
		if (nums[realmid] < target)lo = mid + 1;
		else hi = mid - 1;
	}
	return -1;
}


//Мой код.
Если mid меньше крайнего правого числа, то правая половина отрезка в порядке.Если mid больше крайнего правого числа, то левая половина в порядке. 
Просто оделяем условиями.
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
	    int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
                if (nums[mid] == target)
                    return mid;
                if (nums[mid] < nums[right])
                    if (nums[mid] < target && target <= nums[right])
                        left = mid + 1;
                    else
                        right = mid - 1;
                else
                    if (nums[mid] > target && target >= nums[left])
                        right = mid - 1;
                    else
                        left = mid + 1;
        }
        return -1;
    }
};




//Это обычная реализация бинарного поиска. Поиск в массиве начинается с середины и делится на 2 пока mid не будет равен target. Худшее время O(log n)
int search(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	while (left <= right) {
		int mid = left + (right - left) / 2; //Такое определение помогает избежать переполнения int.
		if(nums[mid] == target)
			return mid;
		if (nums[mid] > target)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}