Algorithm exercise 6

Find Low or High Index

Description

Returns a sorted array of integer types and the lowest and highest indexes where the specified element (key) is located. Returns -1 if the specified element is not in the array. The length of the array is in the millions and allows many overlapping elements.

Example

In the following example, the low index and high index are:

key: 1 low = 0 and high = 0

key: 2 low = 1 and high = 1

key: 5 low = 2 and high = 9

key: 20 low = 10 and high = 10

Tips

Binary Search

Commentary

Runtime Complexity The execution time is O (logn) because it uses Binary Search. Memory Complexity It is a constant O (1). No additional memory is used. However, if Binary Search is implemented recursively, Note that the stack by function call implicitly uses O (logn), memory. However, we will focus on Iteration here.

Thinking

Since the array size is in the millions, the sorted array is O (n) with low index and high index. Linear scanning is very inefficient. Instead, with a few modifications, use Binary Search, Find the low index and high index for a particular key.

Let's look at the algorithm for finding the low index.

1. In every step, consider the sequence between low index and high index. It also calculates the mid index between the low index and the high index.

2. If the element of mid is greater than or equal to key, then high = mid -1. Note that even if the element of mid is the same as key, its index is not necessarily the lowest index.

3. If the element of mid is smaller than key, the array is in ascending order, so key does not exist in the range from the first 0 to mid. Therefore, it may be after mid + 1. low = mid + 1.

4. If low is greater than high, end the iteration and low points to the first occurrence of key. Returns -1 if the low element does not match the key.

Finding the *** high index is similar to the process above. Below is the implementation code. ** **

Implementation

findLowHigh.java

import java.util.List;

public class findLowHigh{

    public int binary_search(List<Integer> arr, int low, int high, int key, boolean search_low){

        while(low <= high) {
            int mid = low + (high - low) / 2;

            if (search_low) {
                if (arr.get(mid) >= key) { // Search the left half for the next
                    high = mid - 1;
                }
                else { // Search the right half for the next
                    low = mid + 1;
                }
            }
            else {
                if (arr.get(mid) <= key) { // Search the left half for the next
                    low = mid + 1;
                }
                else { // Search the right half for the next
                    high = mid - 1;
                }
            }
        }

        if (search_low) {
            if (low == - 1) {
                return low;
            }
            else if (low < arr.size() && arr.get(low) == key) {
                return low;
            }
        } else {
            if (high == -1) {
                return high;
            }
            else if (high < arr.size() && arr.get(high) == key) {
                return high;
            }
        }

        return -1;
    }

    public int find_low_index(List<Integer> arr, int key) {
        return binary_search(arr, 0, arr.size() - 1, key, true);
    }

    public int find_high_index(List<Integer> arr, int key) {
        return binary_search(arr, 0, arr.size() - 1, key, false);
    }
}

Main.java

import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        findLowHigh algorithm = new findLowHigh();

        List<Integer> array = Arrays.asList(1,1,1,2,2,2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,6,6,6);
        int key = 5;
        int low = algorithm.find_low_index(array, key);
        int high = algorithm.find_high_index(array, key);
        System.out.println("LowIndex of " + key + " : "+low);
        System.out.println("HighIndex of " + key + " : "+high);

        key = -2;
        low = algorithm.find_low_index(array, key);
        high = algorithm.find_high_index(array, key);
        System.out.println("LowIndex of " + key + " : "+low);
        System.out.println("HighIndex of " + key + " : "+high);
    }
}

Output