Interpolation Search

Kategori: Popular Algorithms , 19 Kasım 2019 , JanFranco


Problem:

Bir dizideki elementi bulmak.

Yaklaşım:

Brute force yöntemi ile dizinin başından başlayarak sonuna kadar tararız ve tüm elemanları aradığımız eleman ile karşılaştırırız. Daha etkili bir yol seçmek istersek binary search algoritmasını tercih edebiliriz. Binary search algoritmasına alternatif olarak interpolation search yöntemini de kullanabiliriz.

Interpolation Search algoritmasına gerçek hayattan verebileceğimiz örneklerden bir tanesi kitaptaki bir sayfayı bulmak olabilir. Örneğin bir kitabı elimize aldık ve içindekiler kısmından okumak istediğimiz kısmı bulup, sayfayı öğredik. O sayfanın tam olarak konumunu bilmiyoruz bu nedenle o sayfayı ilk denemede açmamız düşük bir şanstır. 500 sayfalık bir kitapta 300. sayfayı açmak istiyoruz diye düşünelim. Tek seferde 300. sayfayı açamayabiliriz ama kitabın yarısından biraz fazlasını açacağımızı biliyoruz. İşte Interpolation Search mantığı da bu şekildedir ve aşağıdaki formül ile çalışır:

x = l + ((v - A[l])*(r - l)) / (A[r] - A[l])

x burada aradığımız değerin indisi, v aradığımız değer, l ve r ise dizinin başındaki ve sonundaki indislerdir. Örneğin bir değer aradık ve x indisini elde ettik. Eğer aradığımız değer o indiste ise direk indisi return edebiliriz. Eğer indis aradığımız değerden büyükse l = x + 1 işlemini yaptıktan sonra algoritmayı tekrar çalıştırabiliriz. Eğer indis aradığımız değerden küçük ise r = x - 1 işlemi yaptıktan sonra algoritmayı tekrar çalıştırabiliriz.

Çözüm:




public class IPNSearch {
	
	public static boolean isSorted(int[] arr) {
		for(int i=0; i<arr.length-1; i++) {
			if(arr[i] > arr[i+1]) {
				return false;
			}
		}
		return true;
	}
	
	public static int interpolationSearch(int[] arr, int x) {
		if(isSorted(arr)) {
			int l = 0, r = arr.length - 1;
			while(r >= l) {
				if(l == r) {
					if(arr[l] == x) {
						return l;
					}
					return -1;
				}
				int pos = l + ((x - arr[l])*(r - l)) / (arr[r] - arr[l]);
				if(arr[pos] == x) {
					return pos;
				}
				else if(arr[pos] < x) {
					l = pos + 1;
				}
				else {
					r = pos - 1;
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] arr = new int[50];
		for(int i=0; i<50; i++) {
			arr[i] = i * 5;
		} 
		System.out.println(interpolationSearch(arr, 55));
	}

}


Sonraki Yazı: Counting One Bits
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın