Linear Search example

🔎 Linear Search (Sequential Search)

What problem are we solving?

Given an array and a target value (the “key”), find the index where the key occurs. If it isn’t present, report that clearly (commonly -1).

When should you use it?

• Arrays or lists that are unsorted (binary search won’t help).

• Small to medium collections where code simplicity matters.

• One-off searches where building an index or sorting is overkill.

How it works (step by step)

1. Start at index 0.

2. Compare the current element to the key.

3. If they match → return the index.

4. Otherwise move to the next element and repeat.

5. If you reach the end with no match → return -1.

Complexity

• Time: O(n) in the worst/average case; O(1) best case (if the key is at index 0).

• Space: O(1) (in-place, no extra memory).

---

Java Implementation

 

package com.vinod.test;

/**
 * LinearSearch (Sequential Search)
 *
 * Problem:
 *   Given an array and a key, return the index of the key if present; otherwise -1.
 *
 * Approach:
 *   Scan from left to right and compare each element with the key.
 *
 * Time Complexity:
 *   Worst/Average: O(n), Best: O(1) if the first element matches.
 *
 * Space Complexity:
 *   O(1)
 *
 * Notes:
 *   - Works on unsorted arrays.
 *   - For sorted arrays, consider Binary Search (O(log n)).
 */
public class LinearSearch {

    public static void main(String[] args) {
        int[] arr = { 1, 3, 5, 7, 9, 12, 16, 18 };

        int key1 = 5;
        int idx1 = indexOf(arr, key1);
        System.out.println("Key " + key1 + " found at index = " + idx1); // expected: 2

        int key2 = 10;
        int idx2 = indexOf(arr, key2);
        System.out.println("Key " + key2 + " found at index = " + idx2); // expected: -1
    }

    /**
     * Returns the zero-based index of {@code key} in {@code arr}, or -1 if not found.
     *
     * @param arr the array to scan (may be unsorted)
     * @param key the value to find
     * @return index of the key if present; otherwise -1
     */
    public static int indexOf(int[] arr, int key) {
        if (arr == null || arr.length == 0) {
            return -1; // handle null/empty safely
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                return i; // found
            }
        }
        return -1; // not found
    }
}

Binary search algorithm and example

🔍 Binary Search (Divide-and-Conquer Algorithm)

What problem are we solving?

When we have a sorted array, we often need to locate a specific value efficiently — for example, to find the index of a student ID or a product code.
Instead of scanning element by element like Linear Search (which takes O(n) time), Binary Search repeatedly divides the search space in half, achieving much faster performance.

---

🧠 How it works (step by step)

1. Precondition: The array must already be sorted (either ascending or descending).

2. Initialize two pointers:

   • start = 0 (beginning of the array)

   • end = arr.length - 1 (end of the array)

3. Find the middle index:
   mid = (start + end) / 2

4. Compare the middle element (arr[mid]) with the key you’re searching for:

   • If arr[mid] == key → ✅ Found → return mid

   • If key < arr[mid] → search left half → set end = mid - 1

   • If key > arr[mid] → search right half → set start = mid + 1

5. Repeat until start > end.
   If the loop ends with no match, the key isn’t present → return -1.

 

package com.vinod.test;


/**
 * Binary search use to find out the position of the elements for the given key.
 *
 * The Array should be either in ascending or decending order. 
 *
 *@authorvinodkariyathungalkumaran
 *
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = { 1, 3, 5, 7, 9, 12, 16, 18 };
        System.out.println("Position of 5=" + getPositionUsingBinarySearch(arr, 5));

    }

    /**
     * Algorithm
     *
     *1) First get the array mid position, if mid position of the value equal to the search key will return that one
     *
     *2) Else if key is less the mid value our start value will be o and end value will be mid -1
     *
     *3) Else if the key is greater than the mid value we will mark our start value as mid value +1
     *
     * This activity we will do until the start and end values are equal.
     *
     *
     *@param arr
     *@param key
     *@return
     */
    public static int getPositionUsingBinarySearch(int[] arr, int key) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (key == arr[mid]) {
                return mid;
            }
            if (key < arr[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}