================================================================================
         DATA STRUCTURES AND ALGORITHMS (C)
         PRACTICAL LAB SESSION 6: Searching & Hashing
         State University of Zanzibar (SUZA)
================================================================================

OBJECTIVES:
- Implement linear search and its variants
- Implement binary search (iterative and recursive)
- Understand hash tables with collision resolution
- Analyze search algorithm performance

================================================================================
PART A: LINEAR SEARCH
================================================================================

1. Basic Linear Search:
   int linearSearch(int arr[], int n, int key);
   Return index of key or -1 if not found.
   Test: [5,3,8,1,9,2] key=8 -> 2

2. Find All Occurrences:
   int findAll(int arr[], int n, int key, int positions[]);
   Return count of occurrences and fill positions array.
   Test: [1,3,5,3,7,3] key=3 -> count=3, positions=[1,3,5]

3. Search in 2D Array:
   int search2D(int mat[][10], int rows, int cols, int key, int *r, int *c);
   Return 1 if found, set row and column.
   Test: [[1,2,3],[4,5,6],[7,8,9]] key=5 -> r=1, c=1

4. Sentinel Search:
   int sentinelSearch(int arr[], int n, int key);
   Place key at end to eliminate bounds check in loop.
   Compare number of comparisons with basic linear search.

5. Find Min and Max in Single Scan:
   void findMinMax(int arr[], int n, int *min, int *max);
   Test: [3,7,1,9,4,6] -> min=1, max=9

================================================================================
PART B: BINARY SEARCH
================================================================================

6. Binary Search (Iterative):
   int binarySearch(int arr[], int n, int key);
   Array must be sorted. Return index or -1.
   Test: [2,5,8,12,16,23,38,56,72,91] key=23 -> 5

7. Binary Search (Recursive):
   int binarySearchRec(int arr[], int low, int high, int key);
   Test: Same array, key=56 -> 7

8. Find First Occurrence:
   int findFirst(int arr[], int n, int key);
   In sorted array with duplicates, find first occurrence.
   Test: [1,2,2,2,3,4,5] key=2 -> 1

9. Find Last Occurrence:
   int findLast(int arr[], int n, int key);
   Test: [1,2,2,2,3,4,5] key=2 -> 3

10. Count Occurrences:
    int countOccurrences(int arr[], int n, int key);
    Use findFirst and findLast.
    Test: [1,2,2,2,3,4,5] key=2 -> 3

11. Search in Rotated Sorted Array:
    int searchRotated(int arr[], int n, int key);
    Test: [4,5,6,7,0,1,2] key=0 -> 4

12. Find Square Root (Integer):
    int mySqrt(int x);
    Use binary search to find floor(sqrt(x)).
    Test: mySqrt(8) -> 2, mySqrt(16) -> 4

================================================================================
PART C: HASHING
================================================================================

Hash Table Structure:
   #define TABLE_SIZE 10
   struct HashNode {
       int key;
       struct HashNode *next;  // for chaining
   };
   struct HashNode *hashTable[TABLE_SIZE];

13. Hash Function:
    int hashFunction(int key);
    Return key % TABLE_SIZE.
    Test: hashFunction(25) -> 5, hashFunction(35) -> 5

14. Hash Table with Chaining:
    Implement insert, search, delete, display.
    void hashInsert(int key);
    int hashSearch(int key);
    void hashDelete(int key);
    void hashDisplay();
    Test: Insert 25, 35, 45, 15 (all hash to 5) -> chain at index 5

15. Hash Table with Linear Probing:
    int table[TABLE_SIZE]; // -1 = empty
    void lpInsert(int key);
    int lpSearch(int key);
    void lpDisplay();
    Handle collision by checking next slot.
    Test: Insert 25, 35 -> 25 at index 5, 35 at index 6

16. Frequency Count Using Hashing:
    Count frequency of each element using a hash table.
    void frequencyCount(int arr[], int n);
    Test: [1,2,1,3,2,1] -> 1:3, 2:2, 3:1

17. Find Duplicates Using Hashing:
    int hasDuplicates(int arr[], int n);
    Use hash table to detect duplicates in O(n).
    Test: [1,2,3,4,5] -> 0, [1,2,3,2,5] -> 1

================================================================================
PART D: EXTRA PRACTICE (LeetCode / HackerRank Style)
================================================================================

18. [Easy] Binary Search (LeetCode 704)
    Given sorted array and target, return index or -1.
    int search(int arr[], int n, int target);

19. [Easy] Search Insert Position (LeetCode 35)
    Find index where target would be inserted in sorted array.
    int searchInsert(int arr[], int n, int target);
    Test: [1,3,5,6] target=5 -> 2, target=2 -> 1, target=7 -> 4

20. [Easy] Two Sum Using Hash (LeetCode 1)
    Given array and target, find two indices using hash table for O(n).
    void twoSumHash(int arr[], int n, int target, int *i, int *j);
    Test: [2,7,11,15] target=9 -> i=0, j=1

21. [Medium] Find Peak Element (LeetCode 162)
    Find a peak element (greater than neighbors) using binary search.
    int findPeakElement(int arr[], int n);
    Test: [1,2,3,1] -> index 2

22. [Medium] Search a 2D Matrix (LeetCode 74)
    Sorted matrix (each row sorted, first of next row > last of prev row).
    int searchMatrix(int mat[][10], int rows, int cols, int target);
    Test: [[1,3,5,7],[10,11,16,20],[23,30,34,60]] target=3 -> 1

23. [Medium] Find Minimum in Rotated Sorted Array (LeetCode 153)
    int findMin(int arr[], int n);
    Test: [3,4,5,1,2] -> 1

24. [HackerRank] Ice Cream Parlor
    Given prices array and money, find two flavors that cost exactly money.
    Use hash table approach.
    Test: prices=[1,4,5,3,2] money=4 -> flavors at indices 0,4 (1+3)

================================================================================