Array Manipulation and Searching

Arrays are fundamental data structures in programming that allow storing a collection of elements of the same type. In competitive programming, efficient array manipulation and searching techniques are essential for solving problems efficiently. In this article, we will explore various techniques for array manipulation and searching using the Java programming language.

Array Manipulation Techniques

Reverse an Array

Reversing an array means changing the order of its elements so that the last element becomes the first, the second last becomes the second, and so on. This can be achieved by swapping the elements from both ends of the array until they meet in the middle.

void reverseArray(int[] arr) {
    int start = 0;
    int end = arr.length - 1;
    while (start < end) {
        // Swap elements
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        
        // Move indices
        start++;
        end--;
    }
}

Rotate an Array

Rotating an array means moving its elements to the left or right by a certain number of positions. To rotate an array to the right, we can reverse the entire array, then reverse the first k elements, and finally reverse the remaining elements.

void rotateArrayRight(int[] arr, int k) {
    int n = arr.length;
    k %= n; // Handle k > n cases
    reverseArray(arr, 0, n-1);
    reverseArray(arr, 0, k-1);
    reverseArray(arr, k, n-1);
}

Insert element into Array

To insert an element at a specific position in an array, we need to shift all elements after the insertion position one step to the right to make room for the new element.

void insertElement(int[] arr, int index, int element) {
    int n = arr.length;
    if (index < 0 || index > n)
        throw new IndexOutOfBoundsException();
    // Shift elements to the right
    for (int i = n-1; i > index; i--) {
        arr[i] = arr[i-1];
    }
    // Insert element
    arr[index] = element;
}

Array Searching Techniques

Linear Search

Linear search is the simplest searching algorithm that traverses the array sequentially, comparing each element with the target element until a match is found or the end of the array is reached.

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

Binary Search

Binary search is a more efficient searching algorithm that works on sorted arrays. It repeatedly divides the search space in half by comparing the target element with the middle element of the array. If the target is smaller, the search continues on the left half; if the target is greater, the search continues on the right half.

int binarySearch(int[] arr, int target) {
    int n = arr.length;
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid; // Element found at index mid
        else if (arr[mid] < target)
            left = mid + 1; // Search on the right half
        else
            right = mid - 1; // Search on the left half
    }
    return -1; // Element not found
}

In conclusion, array manipulation and searching techniques are essential skills for competitive programming. By mastering these techniques and understanding their time complexity, you can efficiently solve problems that involve array manipulation and searching.