Cara yang efisien untuk mencari elemen

Baru-baru ini saya melakukan wawancara, di mana mereka menanyakan pertanyaan " pencarian ".
Pertanyaannya adalah:

Asumsikan ada sebuah array dari (positif) bilangan bulat, yang masing-masing elemen baik +1atau -1dibandingkan dengan elemen yang berdekatan.

Contoh:

array = [4,5,6,5,4,3,2,3,4,5,6,7,8];

Sekarang cari 7dan kembalikan posisinya.

Saya memberikan jawaban ini:

Simpan nilai dalam larik sementara, urutkan, lalu terapkan pencarian biner.

Jika elemen ditemukan, kembalikan posisinya di array sementara.
(Jika nomor tersebut muncul dua kali maka kembalikan kemunculan pertamanya)

Tapi, mereka sepertinya tidak puas dengan jawaban ini.

Apa jawaban yang benar?

Anda dapat melakukan pencarian linier dengan langkah-langkah yang seringkali lebih besar dari 1. Pengamatan penting adalah bahwa jika misalnya array[i] == 4dan 7 belum muncul maka kandidat berikutnya untuk 7 ada pada indeks i+3. Gunakan loop sementara yang berulang kali langsung mengarah ke kandidat berikutnya yang layak.

Ini adalah implementasi, sedikit digeneralisasikan. Ini menemukan kemunculan pertama kdalam array (tunduk pada batasan + = 1) atau -1jika tidak terjadi:

#include <stdio.h>
#include <stdlib.h>

int first_occurence(int k, int array[], int n);

int main(void){
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};
    printf("7 first occurs at index %d\n",first_occurence(7,a,15));
    printf("but 9 first \"occurs\" at index %d\n",first_occurence(9,a,15));
    return 0;
}

int first_occurence(int k, int array[], int n){
    int i = 0;
    while(i < n){
        if(array[i] == k) return i;
        i += abs(k-array[i]);
    }
    return -1;
}

keluaran:

7 first occurs at index 11
but 9 first "occurs" at index -1

Pendekatan Anda terlalu rumit. Anda tidak perlu memeriksa setiap elemen array. Nilai pertama adalah 4, begitu 7juga setidaknya 7-4 elemen, dan Anda dapat melewatkannya.

#include <stdio.h>
#include <stdlib.h>

int main (void)
{
    int array[] = {4,5,6,5,4,3,2,3,4,5,6,7,8};
    int len = sizeof array / sizeof array[0];
    int i = 0;
    int steps = 0;
    while (i < len && array[i] != 7) {
        i += abs(7 - array[i]);
        steps++;
    }

    printf("Steps %d, index %d\n", steps, i);
    return 0;
}

Keluaran program:

Steps 4, index 11

Edit: ditingkatkan setelah komentar dari @Raphael Miedl dan @Martin Zabel.

Variasi dari pencarian linier konvensional bisa menjadi cara yang bagus. Mari kita pilih elemen katakan array[i] = 2. Sekarang, array[i + 1]akan menjadi 1 atau 3 (ganjil), array[i + 2]akan menjadi (hanya bilangan bulat positif) 2 atau 4 (bilangan genap).

Jika terus berlanjut seperti ini, sebuah pola dapat diamati - array[i + 2*n]akan memiliki angka genap sehingga semua indeks ini dapat diabaikan.

Juga, kita bisa melihatnya

array[i + 3] = 1 or 3 or 5
array[i + 5] = 1 or 3 or 5 or 7

jadi, indeks i + 5harus diperiksa berikutnya dan loop sementara dapat digunakan untuk menentukan indeks berikutnya untuk diperiksa, tergantung pada nilai yang ditemukan pada indeks i + 5.

Sementara, ini memiliki kompleksitas O(n)(waktu linier dalam hal kompleksitas asimtotik), ini lebih baik daripada pencarian linier normal dalam istilah praktis karena semua indeks tidak dikunjungi.

Jelas, semua ini akan terbalik jika array[i](titik awal kita) ganjil.

Pendekatan yang disajikan oleh John Coleman adalah apa yang diharapkan pewawancara, kemungkinan besar.
Jika Anda ingin melakukan sedikit lebih rumit, Anda dapat meningkatkan panjang lompatan yang diharapkan:
Panggil nilai target k . Mulailah dengan nilai elemen pertama v pada posisi p dan panggil selisih kv dv dengan nilai absolut av . Untuk mempercepat pencarian negatif, intip elemen terakhir sebagai nilai lain u di posisi o: jika dv × du negatif, k hadir (jika kemunculan k dapat diterima, Anda dapat mempersempit rentang indeks di sini seperti yang dilakukan penelusuran biner). Jika av + au lebih besar dari panjang array, k tidak ada. (Jika dv × du adalah nol, v atau u sama dengan k.)
Menghilangkan validitas Indeks: Probe posisi ( "next") di mana urutan mungkin kembali ke v dengan k di tengah: o = p + 2*av.
Jika dv × du negatif, carilah k (secara rekursif?) Dari p + av ke o-au;
jika nol, u sama dengan k pada o.
Jika du sama dengan dv dan nilai di tengah bukan k, atau au melebihi av,
atau Anda gagal menemukan k dari p + av ke o-au,
biarkan p=o; dv=du; av=au;dan terus menyelidiki.
(Untuk kilas balik penuh ke teks tahun '60 -an, lihat dengan Courier. "Pikiran kedua pertama" saya akan digunakano = p + 2*av - 1, yang menghalangi du sama dengan dv .)

LANGKAH 1

Mulailah dengan elemen pertama dan periksa apakah nilainya 7. Misalkan cadalah indeks posisi saat ini. Jadi, awalnya c = 0.

LANGKAH 2

Jika 7, Anda menemukan indeksnya. Itu c. Jika Anda telah mencapai akhir larik, keluarlah.

LANGKAH 3

Jika tidak, maka 7 harus berada pada |array[c]-7|posisi paling sedikit karena Anda hanya dapat menambahkan satu unit per indeks. Oleh karena itu, Tambahkan |array[c]-7|ke indeks Anda saat ini, c, dan lanjutkan ke LANGKAH 2 lagi untuk memeriksa.

Dalam kasus terburuk, ketika ada alternatif 1 dan -1s, kompleksitas waktu dapat mencapai O (n), tetapi kasus rata-rata akan disampaikan dengan cepat.

Di sini saya memberikan implementasi di java ...

public static void main(String[] args) 
{       
    int arr[]={4,5,6,5,4,3,2,3,4,5,6,7,8};
    int pos=searchArray(arr,7);

    if(pos==-1)
        System.out.println("not found");
    else
        System.out.println("position="+pos);            
}

public static int searchArray(int[] array,int value)
{
    int i=0;
    int strtValue=0;
    int pos=-1;

    while(i<array.length)
    {
        strtValue=array[i];

        if(strtValue<value)
        {
            i+=value-strtValue;
        }
        else if (strtValue==value)
        {
            pos=i;
            break;
        }
        else
        {
            i=i+(strtValue-value);
        }       
    }

    return pos;
}

Berikut ini adalah solusi gaya bagi-dan-taklukkan. Dengan mengorbankan (lebih) pembukuan, kita dapat melewati lebih banyak elemen; daripada memindai dari kiri ke kanan, uji di tengah dan lewati di kedua arah.

#include <stdio.h>                                                               
#include <math.h>                                                                

int could_contain(int k, int left, int right, int width);                        
int find(int k, int array[], int lower, int upper);   

int main(void){                                                                  
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};                                   
    printf("7 first occurs at index %d\n",find(7,a,0,14));                       
    printf("but 9 first \"occurs\" at index %d\n",find(9,a,0,14));               
    return 0;                                                                    
}                                                                                

int could_contain(int k, int left, int right, int width){                        
  return (width >= 0) &&                                                         
         (left <= k && k <= right) ||                                            
         (right <= k && k <= left) ||                                            
         (abs(k - left) + abs(k - right) < width);                               
}                                                                                

int find(int k, int array[], int lower, int upper){                              
  //printf("%d\t%d\n", lower, upper);                                            

  if( !could_contain(k, array[lower], array[upper], upper - lower )) return -1;  

  int mid = (upper + lower) / 2;                                                 

  if(array[mid] == k) return mid;                                                

  lower = find(k, array, lower + abs(k - array[lower]), mid - abs(k - array[mid]));
  if(lower >= 0 ) return lower;                                                    

  upper = find(k, array, mid + abs(k - array[mid]), upper - abs(k - array[upper]));
  if(upper >= 0 ) return upper;                                                  

  return -1;                                                                     

}

const findMeAnElementsFunkyArray = (arr, ele, i) => {
  const elementAtCurrentIndex = arr[i];

  const differenceBetweenEleAndEleAtIndex = Math.abs(
    ele - elementAtCurrentIndex
  );

  const hop = i + differenceBetweenEleAndEleAtIndex;

  if (i >= arr.length) {
    return;
  }
  if (arr[i] === ele) {
    return i;
  }

  const result = findMeAnElementsFunkyArray(arr, ele, hop);

  return result;
};

const array = [4,5,6,5,4,3,2,3,4,5,6,7,8];

const answer = findMeAnElementsFunkyArray(array, 7, 0);

console.log(answer);

Ingin memasukkan solusi rekursif untuk masalah tersebut. Nikmati