// Returns the index of target in arr, or -1 if not found
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// Usage
const arr = [64, 34, 25, 12, 22, 11, 90];
linearSearch(arr, 25);   // → 2  (found at index 2)
linearSearch(arr, 99);   // → -1 (not found)

// Complexity:
// Best case:  O(1) — target is the first element
// Worst case: O(n) — target is last, or not present
// Average:    O(n/2) = O(n) — expected to check half the array
// Space:      O(1) — only two variables (i and comparison result)

// Standard linear search: 2 comparisons per iteration (i < n AND arr[i] === target)
function linearSearchStandard(arr, target) {
  for (let i = 0; i < arr.length; i++) {   // comparison 1: bounds check
    if (arr[i] === target) return i;         // comparison 2: value check
  }
  return -1;
}

// Sentinel optimization: 1 comparison per iteration (only value check)
function linearSearchSentinel(arr, target) {
  const n = arr.length;
  const last = arr[n - 1];    // save the last element
  arr[n - 1] = target;        // place sentinel at end

  let i = 0;
  while (arr[i] !== target) { // only ONE comparison per iteration!
    i++;
  }

  arr[n - 1] = last;          // restore the last element

  if (i < n - 1 || last === target) return i;
  return -1;  // only found the sentinel, not actual target
}

// In practice: JavaScript's JIT compiler often makes this unnecessary.
// The optimization is more valuable in C/C++ or inner loops of critical code.
// Conceptually: it demonstrates that bounds checks have a cost.

// Find the FIRST occurrence (standard)
function findFirst(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// Find the LAST occurrence — scan from the end
function findLast(arr, target) {
  for (let i = arr.length - 1; i >= 0; i--) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// Find ALL occurrences — collect every matching index
function findAll(arr, target) {
  const indices = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) indices.push(i);
  }
  return indices;
}

// Find by CONDITION — more powerful than equality check
function findFirstWhere(arr, predicate) {
  for (let i = 0; i < arr.length; i++) {
    if (predicate(arr[i])) return i;
  }
  return -1;
}

// Example: find first negative number
const nums = [3, 7, -2, 5, -8, 1];
findFirstWhere(nums, x => x < 0);   // → 2 (index of -2)

// JavaScript's built-in equivalents (all use linear scan internally):
nums.indexOf(-2);           // find first: O(n)
nums.lastIndexOf(-2);       // find last: O(n)
nums.findIndex(x => x < 0); // find first by condition: O(n)
nums.filter(x => x < 0);    // find all by condition: O(n), returns [-2, -8]

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Build list: 1 -> 3 -> 5 -> 7 -> 9
const head = new ListNode(1,
  new ListNode(3,
    new ListNode(5,
      new ListNode(7,
        new ListNode(9)))));

// Linear search on linked list: O(n)
function searchLinkedList(head, target) {
  let current = head;
  let index = 0;
  while (current !== null) {
    if (current.val === target) return index;
    current = current.next;
    index++;
  }
  return -1;
}

searchLinkedList(head, 5);   // → 2 (third node)
searchLinkedList(head, 4);   // → -1 (not found)

// Find node by condition
function findNode(head, predicate) {
  let current = head;
  while (current !== null) {
    if (predicate(current.val)) return current;
    current = current.next;
  }
  return null;
}

// Find the middle of a linked list (fast-slow pointer — a form of linear scan)
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;  // slow is at the middle when fast reaches the end
}

// Search in a 2D matrix (unsorted)
function searchMatrix2D(matrix, target) {
  for (let r = 0; r < matrix.length; r++) {
    for (let c = 0; c < matrix[r].length; c++) {
      if (matrix[r][c] === target) return [r, c];
    }
  }
  return [-1, -1];
}

const matrix = [
  [1,  3,  5],
  [7,  9,  11],
  [13, 15, 17],
];
searchMatrix2D(matrix, 9);   // → [1, 1]
searchMatrix2D(matrix, 4);   // → [-1, -1]

// Flatten and search (useful with functional style)
function searchMatrixFlat(matrix, target) {
  return matrix.flat().indexOf(target);  // returns flat index
}

// LeetCode 1 — Two Sum (uses linear search with hash map)
// Given nums and target, find two indices that sum to target.
function twoSum(nums, target) {
  const seen = new Map();  // value → index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
  return [];
}
// O(n) time, O(n) space — one pass linear scan with hash lookup

// Find minimum in unsorted array (linear search for minimum)
function findMin(nums) {
  let min = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < min) min = nums[i];
  }
  return min;
}

// LeetCode 485 — Max Consecutive Ones
// Find the maximum number of consecutive 1s in a binary array
function findMaxConsecutiveOnes(nums) {
  let maxCount = 0, count = 0;
  for (const num of nums) {
    if (num === 1) { count++; maxCount = Math.max(maxCount, count); }
    else count = 0;
  }
  return maxCount;
}
// findMaxConsecutiveOnes([1,1,0,1,1,1]) → 3

// 1. Move-to-front heuristic: if an element is found, move it to the front.
//    Frequently accessed elements accumulate near the start → faster future searches.
function linearSearchMTF(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      if (i > 0) [arr[0], arr[i]] = [arr[i], arr[0]];  // move to front
      return 0;
    }
  }
  return -1;
}

// 2. Frequency ordering: sort elements by access frequency.
//    Accessed often? Near the front. Like a cache.

// 3. Early termination with condition:
//    If you know elements are sorted and target < current, stop early.
function linearSearchSorted(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
    if (arr[i] > target) return -1;  // early exit — target cannot appear later
  }
  return -1;
}