Apakah data awalnya acak..?, misal A={5,2,4,1,3}, trus disuruh cari data
terkecil.Klo datanya blh disort dulu, bukannya udah bs langsung ditemukan hasilnya, dengan mengambil index ke 0...?, dengan asumsi Big O dari sortingnya ga diperhitungkan. "... setelah di sort, index awalnya jadi berantakan. Jadi range [i, j] nya harus disesuaikan juga supaya tetap benar.." Ini maksudnya apa ya..?, bukannya hanya disuruh cari data terkecil di dalam array, dengan proses O (log N), jadi tidak berpengaruh sm index yg berantakan. Tx 2008/6/6 Felix Halim <[EMAIL PROTECTED]>: > 2008/6/6 Felix Halim <[EMAIL PROTECTED] <felix.halim%40gmail.com>>: > > Diberikan array of integer A (0-based index). > > Saya ingin mencari bilangan integer terkecil di array A dengan index > > antara [i, j] (inclusive). > > Jawabannya harus dalam O ( log N ) > > FYI, datanya boleh di preprocess dulu. > Tapi preprocessnya gak boleh O(N^2). > > > Contoh: kalo datanya di sort dulu, itu boleh. > Berarti preprocessing timenya O(N log N). > > > Tapi ingat, setelah di sort, index awalnya jadi berantakan. > Jadi range [i, j] nya harus disesuaikan juga supaya tetap benar. > > 2008/6/6 sm96 <[EMAIL PROTECTED] <syaiful.mukhlis%40gmail.com>>: > > Kalau nyari angka terkecil, harus O(log n), berarti pake cara yg sama > seperti > > binary search > > Solusinya jauh lebih kompleks daripada sekedar binary search. > Datanya harus di-preprocess dahulu untuk mendapatkan structure data > tertentu. > Lalu baru bisa di query untuk angka terkecil antara index [i, j] inclusive. > > Felix Halim > >
