Searching

Linear Search

int[] arr1 = {1,3,4,6,12,3,19,1,3,0,5,4,-1,-12,24,45,1,35,56,6,6,4};
Debug.WriteLine(LinearSearch(arr1, 3));
 
int LinearSearch(int[] arr, int value)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == value) return i;
    }
    return -1;
}

---

Binary Search

Requires a sorted array.

int[] arr = new int[10000];
for (int i = 0; i < arr.Length; i++) arr[i] = i;
 
Debug.WriteLine(BinarySearch(arr, 3342));
 
int BinarySearch(int[] arr, int value)
{
    int left = 0;
    int right = arr.Length - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] == value)
            return mid;           // target found at index mid
        else if (arr[mid] < value)
            left = mid + 1;       // search the right half
        else
            right = mid - 1;      // search the left half
    }
    return -1; // target not found
}

---

Interpolation Search

Works best on uniformly distributed sorted arrays. Uses the value to estimate position rather than always picking the midpoint.

int[] arr = new int[10000];
for (int i = 0; i < arr.Length; i++) arr[i] = i;
 
Debug.WriteLine(InterpolationSearch(arr, 3342));
 
int InterpolationSearch(int[] arr, int value)
{
    int low = 0;
    int high = arr.Length - 1;
    while (low <= high && value >= arr[low] && value <= arr[high])
    {
        // Estimate position using interpolation formula
        int pos = low + (value - arr[low]) / (arr[high] - arr[low]) * (high - low);
        if (arr[pos] == value)
            return pos;           // target found at index pos
        else if (arr[pos] < value)
            low = pos + 1;        // search the right half
        else
            high = pos - 1;       // search the left half
    }
    return -1; // target not found
}

---

Jump Search

Jumps ahead by block size √n, then does linear search within the block.

int[] arr = new int[10000];
for (int i = 0; i < arr.Length; i++) arr[i] = i;
 
Debug.WriteLine(JumpSearch(arr, 3342));
 
int JumpSearch(int[] arr, int value)
{
    int n = arr.Length;
    int m = (int)Math.Floor(Math.Sqrt(n));
    int i = 0;
    // Find the block that contains the target value
    while (i < n && arr[i] < value)
    {
        i += m;
    }
    // Linear search within the previous block
    int startIndex = Math.Max(0, i - m);
    int endIndex = Math.Min(n - 1, i);
    for (int j = startIndex; j <= endIndex; j++)
    {
        if (arr[j] == value) return j;
    }
    return -1; // target not found
}

---

Exponential Search

Finds the range where the target might be by doubling i, then runs binary search within that range.

int[] arr = new int[10000];
for (int i = 0; i < arr.Length; i++) arr[i] = i;
 
Debug.WriteLine(ExponentialSearch(arr, 3342));
 
int ExponentialSearch(int[] arr, int value)
{
    int n = arr.Length;
    if (n == 0) return -1;
    // Find range where target might be present
    int i = 1;
    while (i < n && arr[i] < value)
    {
        i *= 2;
    }
    // Binary search within the found range
    int left = i / 2;
    int right = Math.Min(i, n - 1);
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == value)
            return mid;
        else if (arr[mid] < value)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1; // target not found
}

---

Ternary Search

Divides the array into three parts instead of two. Generally slower than binary search in practice due to more comparisons per iteration.

int[] arr = new int[10000];
for (int i = 0; i < arr.Length; i++) arr[i] = i;
 
Debug.WriteLine(TernarySearch(arr, 3342));
 
int TernarySearch(int[] arr, int value)
{
    int left = 0, right = arr.Length - 1;
    while (left <= right)
    {
        int mid1 = left + (right - left) / 3;
        int mid2 = right - (right - left) / 3;
        if (arr[mid1] == value) return mid1;
        if (arr[mid2] == value) return mid2;
        if (value < arr[mid1])
            right = mid1 - 1;
        else if (value > arr[mid2])
            left = mid2 + 1;
        else
        {
            left = mid1 + 1;
            right = mid2 - 1;
        }
    }
    return -1;
}

---

Fibonacci Search

Uses Fibonacci numbers to divide the array. Avoids division (uses only addition/subtraction), which can be faster on certain hardware.

int[] arr = new int[10000];
for (int i = 0; i < arr.Length; i++) arr[i] = i;
 
Debug.WriteLine(FibonacciSearch(arr, 3342));
 
int FibonacciSearch(int[] arr, int value)
{
    int n = arr.Length;
    int fib2 = 0; // (m-2)th Fibonacci number
    int fib1 = 1; // (m-1)th Fibonacci number
    int fib0 = 0; // mth Fibonacci number
 
    // Find smallest Fibonacci number >= n
    while (fib2 < n)
    {
        fib2 = fib1 + fib0;
        fib0 = fib1;
        fib1 = fib2;
    }
 
    int offset = -1; // starting index of the current sub-array
    while (fib2 > 1)
    {
        int i = Math.Min(offset + fib0, n - 1);
        // Key is smaller — move two Fibonacci steps down
        if (arr[i] > value)
        {
            fib2 = fib0;
            fib1 = fib1 - fib0;
            fib0 = fib2 - fib1;
        }
        // Key is greater — move two Fibonacci steps up
        else if (arr[i] < value)
        {
            fib2 = fib1;
            fib1 = fib0;
            fib0 = fib2 - fib1;
            offset = i;
        }
        // Key found
        else
            return i;
    }
    // Check the last remaining element
    if (fib1 == 1 && arr[offset + 1] == value)
        return offset + 1;
    return -1;
}