Arama Algoritmaları

package main

import (
	"fmt"
	"slices"
)

// linearSearch: O(n)
func linearSearch(data []int, target int) (index, comparisons int) {
	for i, v := range data {
		comparisons++
		if v == target {
			return i, comparisons
		}
	}
	return -1, comparisons
}

// sentinelSearch: sınır kontrolünü ortadan kaldırır (klasik mikro-iyileştirme)
func sentinelSearch(data []int, target int) int {
	if len(data) == 0 {
		return -1
	}
	last := data[len(data)-1]
	data[len(data)-1] = target // nöbetçi: arama mutlaka duracak

	i := 0
	for data[i] != target {
		i++
	}
	data[len(data)-1] = last // diziyi geri yükle

	if i < len(data)-1 || last == target {
		return i
	}
	return -1
}

func main() {
	data := []int{42, 17, 93, 8, 55, 23, 71}

	fmt.Println("dizi:", data)
	for _, target := range []int{42, 55, 71, 100} {
		i, cmp := linearSearch(data, target)
		fmt.Printf("  %-4d ara → indeks=%-3d karşılaştırma=%d\n", target, i, cmp)
	}

	fmt.Println()
	fmt.Println("nöbetçili arama:")
	for _, target := range []int{8, 71, 100} {
		fmt.Printf("  %-4d → indeks=%d\n", target, sentinelSearch(slices.Clone(data), target))
	}

	fmt.Println()
	fmt.Println("standart kütüphane:")
	fmt.Println("  slices.Index(data, 55) =", slices.Index(data, 55))
	fmt.Println("  slices.Contains(data, 93) =", slices.Contains(data, 93))
	fmt.Println("  slices.IndexFunc (ilk 50'den büyük) =",
		slices.IndexFunc(data, func(v int) bool { return v > 50 }))
}

package main

import "fmt"

// binarySearch: iteratif — O(log n), O(1) bellek
func binarySearch(data []int, target int) (index, steps int) {
	lo, hi := 0, len(data)-1

	for lo <= hi {
		steps++
		mid := lo + (hi-lo)/2 // TAŞMA GÜVENLİ: (lo+hi)/2 değil!

		switch {
		case data[mid] == target:
			return mid, steps
		case data[mid] < target:
			lo = mid + 1
		default:
			hi = mid - 1
		}
	}
	return -1, steps
}

// binarySearchRecursive: özyinelemeli — O(log n) bellek (çağrı yığını)
func binarySearchRecursive(data []int, target, lo, hi int) int {
	if lo > hi {
		return -1
	}
	mid := lo + (hi-lo)/2
	switch {
	case data[mid] == target:
		return mid
	case data[mid] < target:
		return binarySearchRecursive(data, target, mid+1, hi)
	default:
		return binarySearchRecursive(data, target, lo, mid-1)
	}
}

func main() {
	data := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
	fmt.Println("sıralı dizi:", data)
	fmt.Println()

	for _, target := range []int{23, 2, 91, 50} {
		i, steps := binarySearch(data, target)
		r := binarySearchRecursive(data, target, 0, len(data)-1)
		fmt.Printf("%-4d → indeks=%-3d adım=%d (özyinelemeli aynı: %t)\n", target, i, steps, i == r)
	}

	// Adım sayısı logaritmik büyür
	fmt.Println()
	fmt.Printf("%12s %10s %14s\n", "eleman", "ikili arama", "doğrusal (en kötü)")
	for _, n := range []int{10, 100, 1_000, 1_000_000, 1_000_000_000} {
		big := make([]int, n)
		for i := range big {
			big[i] = i * 2
		}
		_, steps := binarySearch(big[:min(n, 1_000_000)], -1) // bulunamayan değer: en kötü durum
		if n > 1_000_000 {
			steps = 30 // log₂(10⁹) ≈ 30
		}
		fmt.Printf("%12d %10d %14d\n", n, steps, n)
	}
}

package main

import (
	"fmt"
	"slices"
)

// lowerBound: target'tan KÜÇÜK OLMAYAN ilk elemanın indeksi
func lowerBound(data []int, target int) int {
	lo, hi := 0, len(data) // dikkat: hi = len, len-1 değil
	for lo < hi {
		mid := lo + (hi-lo)/2
		if data[mid] < target {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}

// upperBound: target'tan BÜYÜK ilk elemanın indeksi
func upperBound(data []int, target int) int {
	lo, hi := 0, len(data)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if data[mid] <= target {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}

func count(data []int, target int) int {
	return upperBound(data, target) - lowerBound(data, target)
}

// insertSorted: sıralı diziye sıralı biçimde ekler
func insertSorted(data []int, value int) []int {
	i := lowerBound(data, value)
	return slices.Insert(data, i, value)
}

func main() {
	data := []int{1, 3, 3, 3, 5, 7, 7, 9}
	fmt.Println("dizi:", data)
	fmt.Println()

	fmt.Printf("%8s %12s %12s %8s\n", "değer", "lowerBound", "upperBound", "adet")
	for _, v := range []int{1, 3, 4, 7, 9, 10, 0} {
		fmt.Printf("%8d %12d %12d %8d\n", v, lowerBound(data, v), upperBound(data, v), count(data, v))
	}

	fmt.Println()
	updated := insertSorted(slices.Clone(data), 4)
	fmt.Println("4 eklendikten sonra:", updated)
	updated = insertSorted(updated, 0)
	fmt.Println("0 eklendikten sonra:", updated)
	updated = insertSorted(updated, 100)
	fmt.Println("100 eklendikten sonra:", updated)
}

package main

import (
	"cmp"
	"fmt"
	"slices"
	"sort"
)

type Product struct {
	Name  string
	Price int
}

func main() {
	nums := []int{2, 5, 8, 12, 16, 23, 38}

	// slices.BinarySearch: indeks ve bulunup bulunmadığı
	i, found := slices.BinarySearch(nums, 16)
	fmt.Println("16 →", i, found)

	i, found = slices.BinarySearch(nums, 20)
	fmt.Println("20 →", i, found, "← bulunamadı, ekleneceği yer", i)

	// slices.BinarySearchFunc: özel karşılaştırma
	products := []Product{
		{"kalem", 15}, {"defter", 40}, {"çanta", 250}, {"laptop", 18000},
	}
	j, ok := slices.BinarySearchFunc(products, 250, func(p Product, target int) int {
		return cmp.Compare(p.Price, target)
	})
	fmt.Println("250 TL'lik ürün →", j, ok, products[j].Name)

	// sort.Search: "koşulu sağlayan ilk indeks" — çok genel
	// Koşul false...false,true...true biçiminde olmalı
	firstOver20 := sort.Search(len(nums), func(k int) bool { return nums[k] > 20 })
	fmt.Println("20'den büyük ilk eleman indeksi:", firstOver20, "değer:", nums[firstOver20])

	// sort.Search ile lowerBound
	lower := sort.Search(len(nums), func(k int) bool { return nums[k] >= 12 })
	fmt.Println("12 için lowerBound:", lower)

	// Sıralı olup olmadığını kontrol et: ikili arama ön koşulu
	fmt.Println()
	fmt.Println("dizi sıralı mı:", slices.IsSorted(nums))
	unsorted := []int{3, 1, 2}
	fmt.Println("sırasız dizide arama güvenilir mi:", slices.IsSorted(unsorted))
	badIdx, badFound := slices.BinarySearch(unsorted, 1)
	fmt.Println("sırasız dizide 1 aramak:", badIdx, badFound, "← anlamsız sonuç")
}

package main

import "fmt"

// daysNeeded: verilen hızda kaç gün gerekir
func daysNeeded(chapters []int, speed int) int {
	days, current := 1, 0
	for _, pages := range chapters {
		if current+pages > speed {
			days++
			current = 0
		}
		current += pages
	}
	return days
}

// minSpeed: deadline günde bitirmek için gereken en düşük hız
func minSpeed(chapters []int, deadline int) int {
	lo, hi := 0, 0
	for _, p := range chapters {
		lo = max(lo, p) // en az en uzun bölüm kadar okumalı
		hi += p         // en fazla hepsini bir günde
	}

	for lo < hi {
		mid := lo + (hi-lo)/2
		if daysNeeded(chapters, mid) <= deadline {
			hi = mid // bu hız yeterli, daha azını dene
		} else {
			lo = mid + 1 // yetersiz, artır
		}
	}
	return lo
}

// sqrtInt: tam sayı karekök — cevap üzerinde ikili arama
func sqrtInt(n int) int {
	if n < 2 {
		return n
	}
	lo, hi := 1, n/2+1
	for lo < hi {
		mid := lo + (hi-lo)/2
		if mid*mid <= n {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo - 1
}

// minCapacity: ağırlıkları sırayı bozmadan taşıyacak en küçük gemi kapasitesi
func minCapacity(weights []int, days int) int {
	lo, hi := 0, 0
	for _, w := range weights {
		lo = max(lo, w)
		hi += w
	}

	needed := func(capacity int) int {
		used, load := 1, 0
		for _, w := range weights {
			if load+w > capacity {
				used++
				load = 0
			}
			load += w
		}
		return used
	}

	for lo < hi {
		mid := lo + (hi-lo)/2
		if needed(mid) <= days {
			hi = mid
		} else {
			lo = mid + 1
		}
	}
	return lo
}

func main() {
	chapters := []int{30, 45, 20, 60, 25, 40}
	fmt.Println("bölüm sayfaları:", chapters, "toplam:", 220)

	for _, deadline := range []int{1, 2, 3, 6} {
		speed := minSpeed(chapters, deadline)
		fmt.Printf("  %d günde bitirmek için günde en az %3d sayfa (gerçekte %d gün sürer)\n",
			deadline, speed, daysNeeded(chapters, speed))
	}

	fmt.Println()
	fmt.Println("tam sayı karekök:")
	for _, n := range []int{0, 1, 8, 16, 17, 99, 100, 1_000_000} {
		fmt.Printf("  √%-9d = %d\n", n, sqrtInt(n))
	}

	fmt.Println()
	weights := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println("paket ağırlıkları:", weights)
	for _, d := range []int{1, 5, 10} {
		fmt.Printf("  %2d günde taşımak için gereken kapasite: %d\n", d, minCapacity(weights, d))
	}
}

package main

import "fmt"

// searchRotated: döndürülmüş sıralı dizide arama — O(log n)
func searchRotated(data []int, target int) int {
	lo, hi := 0, len(data)-1

	for lo <= hi {
		mid := lo + (hi-lo)/2
		if data[mid] == target {
			return mid
		}

		if data[lo] <= data[mid] { // sol yarı sıralı
			if data[lo] <= target && target < data[mid] {
				hi = mid - 1 // hedef sıralı yarıda
			} else {
				lo = mid + 1
			}
		} else { // sağ yarı sıralı
			if data[mid] < target && target <= data[hi] {
				lo = mid + 1
			} else {
				hi = mid - 1
			}
		}
	}
	return -1
}

// findRotationPoint: en küçük elemanın indeksi (dönüş noktası)
func findRotationPoint(data []int) int {
	lo, hi := 0, len(data)-1
	for lo < hi {
		mid := lo + (hi-lo)/2
		if data[mid] > data[hi] {
			lo = mid + 1 // en küçük sağda
		} else {
			hi = mid // en küçük mid'de veya solunda
		}
	}
	return lo
}

// findPeak: tepe elemanı bul (komşularından büyük)
func findPeak(data []int) int {
	lo, hi := 0, len(data)-1
	for lo < hi {
		mid := lo + (hi-lo)/2
		if data[mid] < data[mid+1] {
			lo = mid + 1 // yokuş yukarı: tepe sağda
		} else {
			hi = mid // yokuş aşağı: tepe burada veya solda
		}
	}
	return lo
}

func main() {
	rotated := []int{4, 5, 6, 7, 0, 1, 2}
	fmt.Println("döndürülmüş dizi:", rotated)
	fmt.Println("dönüş noktası indeksi:", findRotationPoint(rotated),
		"değer:", rotated[findRotationPoint(rotated)])
	fmt.Println()

	for _, target := range []int{0, 4, 2, 7, 3} {
		fmt.Printf("  %d ara → indeks %d\n", target, searchRotated(rotated, target))
	}

	fmt.Println()
	fmt.Println("farklı dönüş miktarları:")
	for _, d := range [][]int{
		{1, 2, 3, 4, 5},
		{5, 1, 2, 3, 4},
		{3, 4, 5, 1, 2},
		{2, 3, 4, 5, 1},
	} {
		fmt.Printf("  %v → dönüş noktası: %d (en küçük: %d)\n",
			d, findRotationPoint(d), d[findRotationPoint(d)])
	}

	fmt.Println()
	peaks := []int{1, 3, 7, 12, 9, 5, 2}
	p := findPeak(peaks)
	fmt.Println("dizi:", peaks)
	fmt.Println("tepe indeksi:", p, "değer:", peaks[p])
}