Array Manipulation and Searching

Arrays are a fundamental data structure in programming, and understanding how to manipulate and search through them efficiently is crucial for any competitive programmer. In this article, we will explore various techniques for manipulating and searching arrays using C++.

Array Manipulation

Reversing an Array

To reverse an array, we can swap the elements from both ends of the array until we reach the middle. Here's a C++ implementation:

void reverseArray(int arr[], int size) {
    for (int i = 0; i < size / 2; i++) {
        swap(arr[i], arr[size - i - 1]);
    }
}

Rotating an Array

To rotate an array to the right by k positions, we can reverse the whole array, then reverse the first k elements, and finally reverse the remaining elements. Here's a C++ implementation:

void rotateArray(int arr[], int size, int k) {
    k %= size;
    reverseArray(arr, size);
    reverseArray(arr, k);
    reverseArray(arr + k, size - k);
}

Searching in Arrays

Linear Search

The linear search algorithm is the simplest and most basic searching technique. It iterates through the array elements one by one until it finds the desired element. Here's a C++ implementation:

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;  // Element not found
}

Binary Search

Binary search is a fast searching algorithm that works on a sorted array. It repeatedly divides the array in half and compares the middle element with the target value. Here's a C++ implementation:

int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;  // Element not found
}

Binary Search (STL)

C++ provides a built-in binary search function in the Standard Template Library (STL). It can be used with any container that provides random access iterators, including arrays. Here's an example of using the STL binary_search function:

#include <algorithm>
...
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 3;

if (binary_search(arr, arr + size, target)) {
    cout << "Element found!";
} else {
    cout << "Element not found!";
}

Conclusion

Efficient manipulation and searching of arrays are essential skills for competitive programming. Reversing and rotating arrays can be achieved through simple swapping techniques, while searching in arrays can be performed using linear search or the faster binary search algorithm. Additionally, utilizing the built-in functions provided by the C++ Standard Template Library (STL) can simplify and optimize array searching operations.