Oppgave 1

  public static int søkUsortert(int[] a, int verdi)
  {
    int sist = a.length - 1;
    int tmp = a[sist];  // tar vare på den siste
    a[sist] = verdi;    // verdi blir vaktpost

    for (int i = 0; ; i++)  // i < a.length er tatt vekk
      if (verdi == a[i])    // dette blir sant før eller senere
      {
        a[sist] = tmp;  // legger den siste tilbake
        if (i == sist) return verdi == tmp ? sist : -1;
        else return i;
      }
  }

Oppgave 2

for-løkken fortsetter så lenge som a[i] < verdi. Men hvis verdi er mindre enn a[0], kommer den ikke i gang. Siden a[0] da heller ikke er lik verdi, returneres −(0 + 1) = −1.

Hvis tabellen er tom, dvs. a.length lik 0, vil innsettingspunktet for enhver verdi være 0. Dermed skal −1 returneres, og det er nettopp det som skjer.

Søker vi etter 2, 15, 16, 40 og 41 får vi -1, -6, 5, 14 og -16 som returverdier.

Oppgave 3

  // vi leter motsatt vei, dvs. starter bakerst
  public static int lineærsøk(int[] a, int verdi)
  {
    if (a.length == 0 || verdi < a[0])
      return -1;  // verdi er mindre enn den største

    int i = a.length - 1; for( ; a[i] > verdi; i--);

    return verdi == a[i] ? i : -(i + 2);
  }

Oppgave 4

  public static int lineærsøk(int[] a, int fra, int til, int verdi)
  {
    fratilKontroll(a.length, fra, til);

    if (fra == til || verdi > a[til - 1])
      return -(til + 1);  // verdi er større enn den største

    int i = 0; for( ; a[i] < verdi; i++);  // siste verdi er vaktpost

    return verdi == a[i] ? i : -(i + 1);   // sjekker innholdet i a[i]
  }

Oppgave 5 a)

  public static int lineærsøk(int[] a, int k, int verdi)
  {
    if (k < 1)
      throw new IllegalArgumentException("Må ha k > 0!");

    int j = k - 1;
    for (; j < a.length && verdi > a[j]; j += k);

    int i = j - k + 1;  // søker i a[j-k+1:j]
    for (; i < a.length && verdi > a[i]; i++);

    if (i < a.length && a[i] == verdi) return i;  // funnet
    else return -(i + 1);
  }

Oppgave 5 c)

  public static int kvadratrotsøk(int[] a, int verdi)
  {
    return lineærsøk(a,(int)Math.sqrt(a.length),verdi);
  }

Oppgave 6

  public static int[] lineærIntervallsøk(int[] a, int fraverdi, int tilverdi)
  {
    if (a.length == 0 || fraverdi > a[a.length - 1])
      return new int[0];  // returnerer en tom tabell

    int fra = 0;
    while (a[fra] < fraverdi) fra++;

    int til = a.length;

    if (tilverdi <= a[a.length - 1])
    {
      til = fra;
      while (a[til] < tilverdi) til++;
    }

    // intervallet a[fra:til> inneholder de søkte verdiene
    return Arrays.copyOfRange(a, fra, til);
  }