Для сортированного массива, который можно повернуть, найдите в нем элемент с минимальной сложностью времени.
например: Содержимое массива может быть [8, 1, 2, 3, 4, 5]. Предположим, что вы ищете 8 в нем.
Для сортированного массива, который можно повернуть, найдите в нем элемент с минимальной сложностью времени.
например: Содержимое массива может быть [8, 1, 2, 3, 4, 5]. Предположим, что вы ищете 8 в нем.
Решение по-прежнему работает с бинарным поиском в том смысле, что вам нужно разбить массив на две части для проверки.
В отсортированном массиве вы просто смотрите на каждую часть и определяете, живет ли элемент в первой части (позвольте назвать это A) или второй части (B). Поскольку, по определению отсортированного массива, разделы A и B будут отсортированы, это потребует не более чем простых сравнений границ раздела и вашего ключа поиска.
В развернутом сортированном массиве можно гарантировать сортировку только одного из A и B. Если элемент находится внутри части, которая сортируется, то решение прост: просто выполните поиск, как если бы вы делали обычный бинарный поиск. Если, однако, вы должны искать несортированную часть, а затем просто рекурсивно вызывать функцию поиска на не отсортированной части.
В результате получается сложность времени O(lg n)
.
(Реально, я бы подумал, что такая структура данных будет иметь индекс, сопровождающий его, чтобы указать, сколько позиций было повернуто.)
Изменить. Поиск в Google приводит меня к этому несколько устаревшей (но правильной) теме на CodeGuru, где обсуждаются та же проблема. Чтобы добавить к моему ответу, я скопирую некоторый псевдокод, который был указан там, чтобы он появился здесь с моим решением (мышление следует тем же строкам):
Search(set):
if size of set is 1 and set[0] == item
return info on set[0]
divide the set into parts A and B
if A is sorted and the item is in the A range
return Search(A)
if B is sorted and the item is in the B range
return Search(B)
if A is not sorted
return Search(A)
if B is not sorted
return Search(B)
return "not found"
O (log (N))
Уменьшение проблемы поиска наибольшей позиции числа, которая может быть выполнена путем проверки первого и последнего и среднего числа области, рекурсивно уменьшить область, делить и побеждать, Это O (log (N)) no больше, чем двоичный поиск O (log (N)).
EDIT: Например, у вас есть
6 7 8 1 2 3 4 5
^ ^ ^
Посмотрев на 3 числа, которые, как вы знаете, местоположение наименьших/наибольших чисел (будет называться отметкой позже), находится в области 6 7 8 1 2, поэтому 3 4 5 не учитывается (обычно это делается перемещая указатель начала/конца области (int), указывающий на число 6 и 2).
Следующий шаг,
6 7 8 1 2
^ ^ ^
Снова вы получите достаточно информации, чтобы указать, какая сторона (слева или справа) отмечена, затем область уменьшается до половины (до 6 7 8).
Это идея: я думаю, что вы можете уточнить лучшую версию этого, на самом деле, для интервью алгоритм OK с чистым фрагментом кодов лучше, чем лучший алгоритм с кодами OK: на некоторых, чтобы разогреться.
Удачи!
Мне был задан этот вопрос в недавнем интервью. В этом вопросе был описан алгоритм поиска "ключа" в круговом отсортированном массиве. Мне также было предложено написать код для него. Вот что я придумал:
Используйте разделить и победить двоичный поиск. Для каждого подмассива проверьте, отсортирован ли массив. Если отсортировано, используйте классический бинарный поиск например
данные [пуск] < data [end] подразумевает, что данные сортируются. пользовательский двоичный код еще разделите массив до тех пор, пока мы не получим отсортированный массив.
public boolean search(int start,int end){
int mid =(start+end)/2;
if(start>end)
{
return false;
}
if(data[start]<data[end]){
return this.normalBinarySearch(start, end);
}
else{
//the other part is unsorted.
return (this.search(start,mid) ||
this.search(mid+1,end));
}
}
где normalBinarySearch - это простой двоичный поиск.
Это простая модификация нормального двоичного поиска. Фактически мы будем работать как для вращающихся, так и для отсортированных массивов. В случае отсортированных массивов он в конечном итоге сделает больше работы, чем это действительно необходимо.
Для вращающегося массива, когда вы разбиваете массив на два подмассива, возможно, один из этих подмассивов не будет в порядке. Вы можете легко проверить, сортируется ли каждая половина, сравнивая первое и последнее значение в подмассиве.
Зная, отсортирован ли каждый подъярус или нет, мы можем сделать выбор, что делать дальше.
1) отсортированный левый субарфейс, и значение находится в пределах левого подмассива (проверьте оба конца!)
Затем найдите рекурсивно поиск левого подмассива.
2) правый подмашина сортируется, и значение находится в пределах диапазона подправы (проверьте оба конца!)
Затем рекурсивный поиск правого подмассива.
3) left Не отсортировано
Затем рекурсивно выполните поиск в левом подмассиве
4) Не отсортировано правильно
Затем рекурсивный поиск правого подмассива.
Примечание. Разница между этим и обычным двоичным поиском заключается в том, что мы не можем просто выбрать субмассив для рекурсии, просто сравнив последнее значение left subarray (первого значения правого подмассива), чтобы принять наше решение. Значение должно быть строго в левом или правом подмассиве и что подмассива должна сортироваться, в противном случае мы должны рекурсировать на несортированном подмассиве.
Вот несколько Objective-C, которые реализуют это:
@implementation BinarySearcher
- (BOOL)isValue:(int)value inArray:(int[])array withArraySize:(int)size {
return [self subSearchArray:array forValue:value fromIndex:0 toIndex:size -1];
}
- (BOOL)subSearchArray:(int[])array forValue:(int)value fromIndex:(int)left toIndex:(int)right {
if (left <= right) {
int middle = (left + right) / 2;
BOOL leftArraySorted = array[left] <= array[middle];
BOOL rightArraySorted = array[middle + 1] <= array[right];
if (array[middle] == value) {
return YES;
} else if (leftArraySorted && value >= array[left] && value < array[middle]) {
return [self subSearchArray:array forValue:value fromIndex:left toIndex:middle];
} else if (rightArraySorted && value >= array[middle + 1] && value <= array[right]) {
return [self subSearchArray:array forValue:value fromIndex:middle + 1 toIndex:right];
} else if (!leftArraySorted) {
return [self subSearchArray:array forValue:value fromIndex:left toIndex:middle];
} else if (!rightArraySorted) {
return [self subSearchArray:array forValue:value fromIndex:middle + 1 toIndex:right];
}
}
return NO;
}
@end
При любом индексе один раздел будет отсортирован и другой несортирован. Если ключ находится в отсортированном разделе, выполните поиск в отсортированном массиве, иначе в не отсортированном разделе.
BS(lo, hi)
m = (lo + hi)/2
if(k = a[m])
return m
b = 0
if(a[hi] > a[m])
b = 1
if(b)
if(k > a[m] && k<a[hi])
BS(m+1, hi)
else
BS(lo, m-1)
Вот мой подход к нему:
public static int findMin(int[] a, int start, int end){
int mid = (start + end)/2;
if(start == mid){
return a[mid+1];
}else if(a[start] > a[mid]){
return findMin(a, start, mid);
}else if(a[mid+1] > a[start]){
return findMin(a, mid+1, end);
}else{
return a[mid+1];
}
}
Сложность времени: O (log n)
Вы можете обернуть массив классом, который предоставляет только
E get (int index);
и будет вести себя как обычный отсортированный массив. Для ex, если у вас есть 4 5 1 2 3 4, wrapper.get(0) вернет 1.
Теперь вы можете просто повторно использовать решение для двоичного поиска.
Обертка может выглядеть так:
class RotatedArrayWrapper<T> {
int startIndex;
private final List<T> rotatedArray;
public RotatedArrayWrapper(List<T> rotatedArray) {
this.rotatedArray = rotatedArray;
//find index of the smalest element in array
//keep in mind that there might be duplicates
startIndex = ...
}
public T get(int index) {
int size = rotatedArray.size();
if (index > size) throw Exception...
int actualIndex = (startIndex + index) % size;
return rotatedArray.get(actualIndex);
}
}
Реализация Python. Можно использовать более pythonic:
from bisect import bisect_left
def index(a, x):
"""Binary search to locate the leftmost value exactly equal to x.
see http://docs.python.org/2/library/bisect.html#searching-sorted-lists
>>> index([5, 14, 27, 40, 51, 70], 27)
2
>>> index([1, 2, 3, 4], 10)
Traceback (most recent call last):
...
ValueError
"""
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def _index_shifted(value, sequence, start, stop):
"""Recursive reset location and binary search"""
# if at reset (min) and it not the value, it not there
if start == stop and sequence[start] != value:
return -1
mid = (stop + start) // 2
# check mid, since we are already here
if sequence[mid] == value:
return mid
# right side is sorted
elif sequence[mid] < sequence[stop]:
# if value falls in range, search righ
if sequence[stop] >= value > sequence[mid]:
return index(sequence[mid:stop + 1], value) + mid
# partition left side
return _index_shifted(value, sequence, start, mid)
# left side is sorted
else:
# if value falls in range, search left
if sequence[mid] > value >= sequence[start]:
return index(sequence[start:mid], value) + start
# partition right side
return _index_shifted(value, sequence, mid + 1, stop)
def index_shifted(sequence, value):
"""Returns index of value in a shifted sorted sequence; -1 if not present.
>>> index_shifted([10, 13, 16, 19, 22, 25, 28, 31, 34, 37], 10)
0
>>> index_shifted([10, 13, 16, 19, 22, 25, 28, 31, 34, 37], 37)
9
>>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 10)
2
>>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 37)
1
>>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 13)
3
>>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 25)
7
>>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], 10)
5
>>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], -10)
-1
>>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], 100)
-1
"""
return _index_shifted(value, sequence, 0, len(sequence) - 1)
//это решение делит массив на два равных подмассива с использованием recurssion и применяет двоичный поиск в отдельном отсортированном массиве и продолжает делиться несортированным массивом
public class SearchRotatedSortedArray
{
public static void main(String... args)
{
int[] array={5,6,1,2,3,4};
System.out.println(search(array,Integer.parseInt(args[0]),0,5));
}
public static boolean search(int[] array,int element,int start,int end)
{
if(start>=end)
{
if (array[end]==element) return true;else return false;
}
int mid=(start+end)/2;
if(array[start]<array[end])
{
return binarySearch(array,element,start,end);
}
return search(array,element,start,mid)||search(array,element,mid+1,end);
}
public static boolean binarySearch(int[] array,int element,int start,int end)
{
int mid;
while(start<=end)
{
mid=(start+end)/2;
if(array[mid]==element)
return true;
if(array[mid]<element)
{
start=mid+1;
}
else
{
end=mid-1;
}
}
return false;
}
}
int findIndexInRotatedSort( vector<int> input, int s, int e, int toFind )
{
if (s > e || s >= input.size() || e < 0)
{
return -1;
}
int m = (s + e)/2;
int sVal = input.at(s);
int eVal = input.at(e);
int mVal = input.at(m);
if (sVal == toFind)
return s;
if (eVal == toFind)
return e;
if (mVal == toFind)
return m;
bool isFirstOrdered = (sVal < mVal);
bool isSecondOrdered = (mVal < eVal);
if (toFind > mVal)
{
if (!isSecondOrdered || toFind < eVal)
{
return findIndexInRotatedSort( input, m+1, e, toFind );
}
else
{
return findIndexInRotatedSort( input, s, m-1, toFind );
}
}
else
{
if (!isFirstOrdered || toFind > sVal)
{
return findIndexInRotatedSort( input, s, m-1, toFind );
}
else
{
return findIndexInRotatedSort( input, m+1, e, toFind );
}
}
}
public class RoatatedSorted {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] rotArray = {5,6,7,8,9,10,15,16,17,1,2,3,4,};
search(rotArray,0,rotArray.length-1,10);
}
private static void search(int[] a, int low, int high,int key) {
//int mid = low + (high-low)/2;
//if(a[mid]==a[key]){System.out.println("element found at" + key+1 +" position"); return;}
// find pos to split array
int pos = findSplitIndex(a,low,high);
System.out.println("split pos found at" + pos +" position");
if(key>=a[low]&& key <=a[pos])
bsearch(a,low,pos,key);
if(key>=a[pos+1]&& key <=a[high])
bsearch(a,pos+1,high,key);
}
private static void bsearch(int[] a, int low, int high,int key) {
// TODO Auto-generated method stub
if(low>high) return;
int mid = low + (high-low)/2;
if(a[mid]==key)
{System.out.println("element found at" + ++mid +" position"); return;}
if(a[mid] > key)
bsearch(a,low,mid-1,key);
if(a[mid]<key)
bsearch(a,mid+1,high,key);
}
private static int findSplitIndex(int[] a, int low, int high) {
// TODO Auto-generated method stub
int mid;
if(low>high)return -1;
while(true) {
mid = low + (high-low)/2;
if( a[mid]>a[mid+1])
break;
if(a[mid]>a[low])
low=mid;
if(a[high]>a[mid])
high=mid;
}
return mid;
}
}
Сначала, чтобы найти элемент Minimum в массиве, разделите массив на две части. После этого поиска заданное значение используется двоичным деревом поиска. Сложность: O (logn) Если вам нужно найти элемент Minimum во вращающемся массиве, используйте тот же подход, просто пропустите двоичный поиск. Сложность: O (logn)
//Search an element in a sorted and pivoted array
class SearchInPivotedSortedArray
{
//searchInOrtedPivotedArray : Return index of matched element with given value.
public static int searchInSortedPivotedArray(int[] A, int value)
{
int min = findMinElement(A,0,A.Length-1);
if (min == A[0])
return binarySearchTree(A, 0, A.Length-1, value);
if (value <= A[A.Length-1])
return binarySearchTree(A, min, A.Length-1, value);
else
return binarySearchTree(A, 0, min-1, value);
}
//return index of Pivot element
public static int findMinElement(int[] Array, int low, int high)
{
if (low >= high)
return low;
int mid = (low + high) / 2;
if (mid > low && Array[mid] < Array[mid - 1])
return mid;
if (mid < high && Array[mid] > Array[mid + 1])
return mid + 1;
if (Array[mid] < Array[high])
return findMinElement(Array, low, mid - 1);
return findMinElement(Array, mid + 1, high);
}
//Return match element index, if not found return -1
public static int binarySearchTree(int[] array, int low, int high,int value)
{
if (low > high)
return -1;
int mid = (low + high)/2;
if (array[mid] == value)
return mid;
if (array[mid] > value)
return binarySearchTree(array, low, mid - 1, value);
else
return binarySearchTree(array, mid + 1, high, value);
}
}
это решение O (logn): проверено. он работает как с отсортированными, так и с повернутыми сортированными массивами:
public static int rbs(int[] a, int l, int r, int t) {
if (a[l] <= a[r]) {
return bs(a, l, r, t);
}
if (r < l) {
return -1;
} else {
int m = (l+r) / 2;
if (a[m] == t) {
return m;
} else if (a[m] > t) { // check left half
if (a[l] > a[m]) { // left is unsorted
return rbs(a, l, m-1, t);
} else { // left is sorted
if (a[l] < t) { // t is in range
return bs(a, l, m-1, t);
} else if (a[l] > t) { // t is out of range on left
if (a[r] >= t) {
return rbs (a, m+1, r, t);
} else
return -1;
} else
return l;
}
} else { // other side
if (a[r] < a[m]) { // right is unsorted
return rbs(a, m+1, r, t);
} else { // right is sorted
if (a[r] > t) { // t is in range
return bs(a, m+1, r, t);
} else if (a[r] < t) { // t is out of range on right side
if (a[l] <= t) {
return rbs (a, l, m-1, t);
} else
return -1;
} else
return r;
}
}
}
}
public static int bs(int[] a, int l, int r, int t) {
int m = (l+r) / 2;
if (r < l) {
return -1;
} else {
if (a[m] == t)
return m;
else if (a[m] < t)
return bs(a, m+1, r, t);
else
return bs (a, l, m-1, t);
}
}
Попробуйте это решение,
public static int findElement(int[] a, int key, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (key == a[mid]) {
return mid;
} else if (key < a[mid]) {
return (a[left] <= a[mid] && a[left] < key ? findElement(
a, key, left, mid - 1) : findElement(a, key,
mid + 1, right));
} else {
return (a[mid] <= a[right] && a[right] < key ? findElement(
a, key, left, mid - 1) : findElement(a, key,
mid + 1, right));
}
}
Вот реализация ответа на @Andrew Song на С++
int search(int A[], int s, int e, int k) {
if (s <= e) {
int m = s + (e - s)/2;
if (A[m] == k)
return m;
if (A[m] < A[e] && k > A[m] && k <= A[e])
return search(A, m+1, e, k);
if (A[m] > A[s] && k < A[m] && k >= A[s])
return search(A, s, m-1, k);
if (A[m] < A[s])
return search(A, s, m-1, k);
if (A[m] > A[e])
return search(A, m+1, e, k);
}
return -1;
}
Это 100% работающее и протестированное решение в PYTHON
Программа для поиска номера из отсортированного, но повернутого массива
def findNumber(a, x, start, end):
if start > end:
return -1
mid = (start + end) / 2
if a[mid] == x:
return mid
## Case : 1 if a[start] to a[mid] is sorted , then search first half of array
if a[start] < a[mid]:
if (x >= a[start] and x <= a[mid]):
return findNumber(a, x, start, mid - 1)
else:
return findNumber(a,x, mid + 1, end)
## Case: 2 if a[start] to a[mid] is not sorted , then a[mid] to a[end] mist be sorted
else:
if (x >= a[mid] and x <= a[end]):
return findNumber(a, x, mid + 1, end)
else:
return findNumber(a,x, start, mid -1)
a = [4,5,6,7,0,1,2]
print "Your array is : " , a
x = input("Enter any number to find in array : ")
result = findNumber(a, x, 0, len(a) - 1)
print "The element is present at %d position: ", result
def search (массив, левый, правый, целевой): # Остановить условия для рекурсии. if not array: return -1 если left == right: return left if array [left] == target else -1
# Check if middle element is same as the target.
mid = (left + right) / 2
if array[mid] == target:
return mid
# Pivot point is at the right of the middle element.
if array[left] <= array[mid]:
if target >= array[left] and target <= array[mid]:
return search(array, left, mid - 1, target)
return search(array, mid + 1, right, target)
# Pivot point is at the left of the middle element.
if target >= array[mid] and target <= array[right]:
return search(array, mid + 1, right, target)
return search(array, left, mid - 1, target)
Я нашел решение от этот пост
Мое решение: эффективность: O (logn)
public static int SearchRotatedSortedArray(int l, int d, int[] array, int toFind) {
if (l >= d) {
return -1;
}
if (array[l] == toFind) {
return l;
}
if (array[d] == toFind) {
return d;
}
int mid = (l + d) / 2;
if (array[mid] == toFind) {
return mid;
}
if ((array[mid] > toFind && toFind > array[l]) || (array[mid] < toFind && array[d] < toFind)) {
return SearchRotatedSortedArray(l, mid - 1, array, toFind);
} else {
return SearchRotatedSortedArray(mid + 1, d, array, toFind);
}
}
#include<iostream>
using namespace std;
int BinarySearch(int *a,int key, int length)
{
int l=0,r=length-1,res=-1;
while(l<=r)
{
int mid = (l+r)/2;
if(a[mid] == key) {res = mid; break;}
//Check the part of the array that maintains sort sequence and update index
// accordingly.
if((a[mid] < a[r] && ( key > a[mid] && key <=a[r]))
|| a[mid] > a[r] && !( key>=a[l] && key <a[mid]))
{
l = mid+1;
}
else r = mid-1;
}
return res;
}
void main()
{
int arr[10] = {6,7,8,9,10,13,15,18,2,3};
int key = 8;
cout<<"Binary Search Output: "<<BinarySearch(arr,key,10);
}
Найти индекс элемента во вращающемся отсортированном массиве
Example : [6,7,8,1,2,3,5]
int findElementIndex(int []a, int element, int start, int end)
{
int mid = (start + end)>>1;
if(start>end)
return -1;
if(a[mid] == element)
return mid;
if(a[mid] < a[start])
{
if(element <= a[end] && element > a[mid])
{
return findElementIndex(a,element,mid+1,end);
}
else{
return findElementIndex(a,element,start,mid-1);
}
}
else if(a[mid] > a[start]){
if(element >= a[start] && element < a[mid])
return findElementIndex(a,element,start,mid-1);
else
return findElementIndex(a,element,mid+1,end);
}
else if (a[mid] == a[start]){
if(a[mid] != a[end]) // repeated elements
return findElementIndex(a,element,mid+1,end);
else
int left = findElementIndex(a,element,start,mid-1);
int right = findElementIndex(a,element,mid+1,end);
return (left != -1) ? left : right;
}
}