Binary Search Algorithm

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


Problem:

Kullanıcının belirlediği bir sayıyı dizide aratmak istediğimizi düşünelim. Klasik yaklaşımımızda baştan veya sondan başlarız ve tüm elemanları karşılaştırırız ta ki elemanı bulana kadar. Bu problemimize daha etkili bir yol arıyoruz.

Yaklaşım:

Dizinin sıralı olduğunu düşünürsek, diziyi ikiye bölebiliriz ve ortadaki sayı ile aradığımız sayıyı karşılaştırabiliriz. Eğer aradığımız sayı ortadaki sayı ise ilk denemede bulduk demektir. Eğer aradığımız sayı dizinin sağ tarafındaysa, aynı işlemleri sağ tarafta, sol tarafındaysa aynı işlemleri sol tarafta yapacağız. Sahte kodu inceleyelim:

ALGORITHM BinarySearch(A[0..n -1 ], K)

l <- 0, r <- n - 1
while l <= r do
    m <- (l + r)/2
    if K = A[m] return m
    else if K < A[m]
        r <- m - 1
    else l <- m + 1
return -1

Çözüm:




public class BinarySearch {
	
	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 binarySearch(int[] arr, int k) {
		if(isSorted(arr)) {
			int right = arr.length - 1, left = 0;
			while(right >= left) {
				int middle = left + (right - left) / 2;
				if(k == arr[middle]) {
					return middle;
				}
				else if(k > arr[middle]) {
					left = middle + 1;
				}
				else if(k < arr[middle]) {
					right = middle - 1;
				}
				middle = ((right - left) / 2) + left;
			}
			return -1;
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] myArr = {1, 3, 9, 12, 24, 36, 48, 55};
		System.out.println(binarySearch(myArr, 36));
	}

}


Sonraki Yazı: Quick Select
Yorumlar

Henüz bir yorum bulunmuyor.