Nuputamiseks: Otsing ringpuhvris

PHP-s

function find_min_element($arr) {
  $count = count($arr);
  $min = $arr[0];
  for($i=1;$i<$count;$i++) {
    if ($min > $arr[$i]) {
      $min = $arr[$i];
      $res = $i;
      break;
    }
  }
  return $res;
}

function find_element($arr,$el) {
  $count = count($arr);
  for($i=0;$i<$count;$i++) {
    if ($el == $arr[$i]) {
      $res = $i;
      break;
    }
  }
  return $res;
}

Kuna tegemist Googli küsimusega, siis läksin kaasa viimase hullusega ning kirjutasin lahenduse Go keeles.

Kummagi funktsiooni puhul kasutatakse natuke modifitseeritud varianti kahendotsingust. Seega kumbki peaks halvimal juhul olema O(log(n)).

Täiesti suurepäraselt sobisid selle ülesande jaoks Go tükid (slice), mis võimaldavad effektiivselt anda funktsioonile edasi valitud tükikese massiivist. Näiteks kui allolevas koodis on array[0:m] siis mitte ei looda uut massiivi, mis sisaldab vana massiivi elemente 0 kuni m-1, vaid luuakse justnagu alammassiiv, mis teab et ta on osa sellest suurest massiivist, kuid käitumise poolest on see justnagu päris massiiv, välja arvatud, et kui sa sellele omistad, siis muutuvad ka alloleva massiivi elemendid.

package main

import "fmt"
import "math"

// Returns two values:
// - index of the needle
// - true on success, false when not found
func find(array []int, needle int) (int, bool) {
    length := len(array);

    // When empty array, then not found.
    if length == 0 {
        return 0, false
    }

    // Find the middle of the array
    m := length / 2;

    // remember the beginning and end of first half of the array
    begin := array[0];
    middle := array[m];

    switch {
    // Answer found when needle at the beginning or middle of array
    case begin == needle:
        return 0, true
    case middle == needle:
        return m, true

    // When first half is sequencial and contains needle
    case begin < needle && needle < middle:
        return find(array[0:m], needle)

    // When first half not sequencial and contains needle
    case begin > middle && (needle > begin || needle < middle):
        return find(array[0:m], needle)
    }

    // Otherwise must be in second half.
    index, ok := find(array[m+1:length], needle);
    return index + m + 1, ok;
}

// Returns index of smallest array element
func min(array []int) int {
    length := len(array);

    // We know the answer for 1..2 element arrays
    if length <= 2 {
        if length == 1 || array[0] < array[1] {
            return 0
        } else {
            return 1
        }
    }

    // We also know the answer when the whole array is
    // sequentially sorted
    if array[0] < array[length-1] {
        return 0
    }

    // Find the middle index of the array
    m := length / 2;

    // The smallest element must be in this half of array
    // that is not sequencially sorted.

    // Is the first half non-sequencial?
    if array[0] > array[m] {
        return min(array[0 : m+1])
    }
    // So it must be the second half.
    return m + min(array[m:length]);
}

func main() {
    arr := []int{5, 6, 7, 9, 10, 1, 2, 3, 4};
    needle := 3;

    index, ok := find(arr, needle);
    if ok {
        fmt.Printf("Found at %d\n", index)
    } else {
        fmt.Printf("Not found\n")
    }

    fmt.Printf("Minimum at %d\n", min(arr));
}

Siin on siis minu käkerdis :D... (enda väikesed testid pidas vastu). Mõlemad algoritmid ruumis O(1) ja kiirus O(logN).

def findMin(a):
	b = 0
	e = len(a)-1
	while e - b > 0:
		m = (b + e) / 2
		if a[b] > a[m]:
			e = m
		elif a[m] > a[e]:
			b = m+1
		else:
			return a[b]
	return a[e]

def binS(a, v, b, e):
	while b < e:
		m = ( b + e ) / 2
		mv = a[m]
		if mv < v:
			b = m + 1
		elif mv > v: 
			e = m
		else:
			return m
	if a[e] == v:
		return e
	else:
		return -1

def findVal(a, v):
	b = 0
	e = len(a)-1
	while b < e:
		m = (b + e) / 2
		mv = a[m]
		ab = a[b]
		if ab > mv:
			if (v >= mv) & (v <= a[e]):
				return binS(a, v, m, e)
			else:
				e = m
		elif mv > a[e]:
			if (v <= mv) & (v >= ab):
				return binS(a, v, b, m)
			else:
				b = m
		else:
			return binS(a, v, b, e)
	if a[e] == v:
		return e
	else:
		return -1

Teeme siis lühidalt:

def findmax(a, start=0, rlen=0):
  test=(a[start]<=a[start+rlen/2-1]) and (a[start+rlen/2-1] < a[start+rlen/2])
  return (start+rlen-1) if rlen <= 1 else findmax(a,start+test*(rlen/2), (rlen/2)+test*(rlen % 2))


def findval(a, val, start=0, rlen=0):
  test=((a[start+rlen/2] <= v) and (v <= a[start+rlen-1])) or \
       ((a[start+rlen/2] > a[start+rlen-1]) and ((a[start+rlen/2] <= v) or (a[start+rlen-1] >= v)))
  return (start+rlen-1) if rlen <= 1 else findval(a,val,start+test*(rlen/2), (rlen/2)+test*(rlen % 2))

Või siis nüüd üldisemalt:

def bsearch(x, start, rlen, test):
  t = test(x,start,rlen)
  return (start+rlen-1) if rlen <= 1 else bsearch(x,start+t*(rlen/2), (rlen/2)+t*(rlen % 2), test)


testmax = lambda a,start,rlen: (a[start]<=a[start+rlen/2-1]) and (a[start+rlen/2-1] < a[start+rlen/2])
findmax = lambda a: bsearch(a,0,len(a),testmax)

testval = lambda (a,v),start,rlen: ((a[start+rlen/2] <= v) and (v <= a[start+rlen-1])) or \
                         ((a[start+rlen/2] > a[start+rlen-1]) and ((a[start+rlen/2] <= v) or (a[start+rlen-1] >= v)))
findval = lambda a,v: bsearch((a,v),0,len(a),testval)

Haskelli versioon:

-- Leiab v2ikseima elemendi positsiooni  
findMin :: Ord a => [a] -> Maybe Int  
findMin [] = Nothing  
findMin xs = let sorted = qsort xs  
             in scan 0 (head sorted) xs  


-- Leiab otsitava elemendi, tagastab positsiooni  
findVal :: Eq a => a -> [a] -> Maybe Int  
findVal x xs = scan 0 x xs  


{- otsib spetsifitseeritud elemendi positsiooni  
   i = positsioon e. index  
   x = otsitav element  
   (y:ys) = massiiv  
-}  
scan :: Eq a => Int -> a -> [a] -> Maybe Int  
scan _ _ [] = Nothing  
scan i x (y:ys) | x == y = Just i  
                | otherwise = scan (i+1) x ys  


-- Tavaline quicksort algoritm  
qsort :: Ord a => [a] -> [a]  
qsort (x:xs) = smaller xs ++ [x] ++ larger xs  
               where  
                  smaller xs = [a | a <- xs, a < x]  
                  larger xs = [b | b <- xs, b >= x]

Testid interpretaatoris:

*Main> findMin [5,6,7,1,2,3,4]  
Just 3  
*Main> findVal 2 [5,6,7,1,2,3,4]  
Just 4  
*Main> findVal 9 [5,6,7,1,2,3,4]  
Nothing  
*Main> findMin []  
Nothing

find_min siis minupoolt

#include <iostream>
using namespace std;


int find_min(int arr[], int len)
{
    int left_bound = 0;
    int right_bound = len - 1;
    bool b = false;

    if(len == 1 || (b=true && arr[0] > arr[1]))
    	return arr[b];

    while(true)
    {
    	int l = (right_bound + left_bound) / 2;
    	if(right_bound - left_bound <= 0 ||
                     (arr[l - 1] > arr[l] && arr[l] < arr[0]))
    		return min(arr[0], arr[l]);

    	arr[0] < arr[l] ? (left_bound = l + 1) : (right_bound = l);
    }
}

int main()
{
    int arr[] = {5,6,7,1,2,3,4};
    int ars = sizeof(arr) / sizeof arr[0];
    cout << find_min(arr, ars);
    return 0;
}

C# variant:

class RingPuhver
{
    public static int FindMin(int[] array)
    {
        return Array.IndexOf(array, array.Min());
    }
    public static int FindVal(int[] array, int value)
    {
        return Array.IndexOf(array, value);
    }
}

Kommentaar Avo lahendusele: ei oska mina midagi paremat pakkuda, aga minimaalse leidmisel võiks olla kõigepealt ka kontroll sellisele juhule, kus puhver on (juhuslikult) sorditud:

if A[R] > A[L] then
  Result := 0

Reaalsed ringpuhvrid evivad sageli lisaks pesadele ka viita puhvri "sisulisse" algusse. Viide Google suunas tähendab ilmselt, et selles ülesandes niisugust viita ei ole (muidu oleks tegemist Microsofti ülesandega), aga kuna puhvri vähima elemendi positsiooni teadaolemine ülesande sisu oluliselt mõjutab, oleks see ilus ilmutatult ära mainida.