Arrays -chapter 4

Search in an Array

There's more than one way of searching an Array, but for now, we're going to focus on the simplest way. Searching means to find an occurrence of a particular element in the Array and return its position. We might need to search an Array to find out whether or not an element is present in the Array. We might also want to search an Array that is arranged in a specific fashion to determine which index to insert a new element at.

 

1. Linear Search

we can check every element in the Array. This technique for finding an element by checking through all elements one by one is known as the linear search algorithm. In the worst case, a linear search ends up checking the entire Array. Therefore, the time complexity for a linear search is O(N).

Let's see the linear search algorithm in action, with all the edge cases handled properly. When we say edge cases, we basically mean scenarios that you wouldn't expect to encounter.

For example, the element you're searching for might not even exist in the Array. Or, an even rarer, but possible, scenario is that the input Array doesn't contain any elements at all, or perhaps it is null. It's important to handle all of these edge cases within the code.

 

public static boolean linearSearch(int[] array, int length, int element) {
    // Check for edge cases. Is the array null or empty?
    // If it is, then we return false because the element we're
    // searching for couldn't possibly be in it.
    if (array == null || length == 0) {
        return false;
    }

    // Carry out the linear search by checking each element,
    // starting from the first one.
    for (int i = 0; i < length; i++) {
        // We found the element at index i.
        // So we return true to say it exists.
        if (array[i] == element) {
            return true;
        }
    }

    // We didn't find the element in the array.
    return false;
}

 

2. Binary Search

 If the elements in the Array are in sorted order, then we can use binary search.  Binary search is where we repeatedly look at the middle element in the Array, and determine whether the element we're looking for must be to the left, or to the right. The downside of binary search though is that it only works if the data is sorted.

 

 

Check If N and Its Double Exist (36.57%) 

linear search로 풀었기 때문에 효율이 그닥 좋지 못하다. 그렇다고 sorted array가 아니라 binary search를 사용할 수 없음. (Array.sort 사용해서 할 수 있으나..... 시간은...?

class Solution {
    public boolean checkIfExist(int[] arr) {
        int len = arr.length;
        
        for(int i = 0; i<len-1;i++){
            for(int j = i+1;j<len;j++){
                if(arr[i] == arr[j] *2 || arr[j] == arr[i] *2){
                    return true;
                }
            }
        }
        return false;
    }
}

아니!!!!!!! 자바에서 Arrays.binarySearch( array, value)가 있넼ㅋㅋㅋㅋㅋㅋㅋㅋ

이제껏 몰랐다니...ㅜㅜ

이렇게 하면 같은 찾고자 하는 value값의 index를 알려준다.

만약에 value가 없거나 1개보다 많은 경우에는 음수를 출력한다.

<

value가 없고 value가 array에 있는 하나 이상의 요소보다 작은 경우 value보다 큰 첫째 요소 인덱스의 비트 보수인 음수가 반환됩니다. value가 없고 value가 array에 있는 모든 요소보다 큰 경우 마지막 요소에 1을 더한 인덱스의 비트 보수인 음수가 반환됩니다.

>

 

그런데 효율적으로는 좋지 못한 듯... (21.54%)

public boolean checkIfExist(int[] arr) {
	Arrays.sort(arr);

	for (int i = 0, n = arr.length; i < n; i++)
		if (arr[i] == 0) {
			if (i + 1 < n && arr[i + 1] == 0)
				return true;
		} else if (Arrays.binarySearch(arr, arr[i] * 2) >= 0) {
			return true;
		}

	return false;
}

 

3. 다른 방법으로는 map을 활용한 방법도 있었다.

 

public boolean checkIfExist(int[] arr) {
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < arr.length; i++) {
            
            if(map.get(arr[i]) != null) return true;
            else  {
                if(arr[i]% 2 == 0) map.put((arr[i] / 2) , arr[i]);
                map.put(arr[i] * 2, arr[i]);
            }
            
        }
        
        return false;
        
    }

 

Valid Mountain Array (22.10%)

:모든 케이스의 edge cases  구하기가 너무 어렵다ㅜㅜ

다른 방법을 강구해야...

 

 

class Solution {
    public boolean validMountainArray(int[] arr) {
        //edge cases 전부 cover하는 게 중요
        boolean increasing = true;
        int count = 0;
        if(arr.length<3) {
            return false;
        }
        
        for(int i = 1; i<arr.length;i++){
            if(arr[i] <arr[i-1]){
                if(increasing == true ) {
                    if(i==1) {
                        return false;
                    }
                    increasing = false;
                    count++;
                } 
            } else if(arr[i] == arr[i-1]){
                return false;
            }else {
                if(!increasing) {
                    return false;
                }
            }
        }
        if(!increasing && count==1){
            return true;
        }
        return false;     
    }
}

 

 

2번째 방법(100%)

결국 increasing과 decreasing 에서는 sorted 되어있다는 뜻이기 때문에 binary search 사용 가능하다!!!!

maxIndex를 기준으로 왼쪽은 계속 maxIndex까지 increasing

오른쪽은 maxIndex부터 계속 decreasing 되어야 한다.

 

class Solution {
   public boolean validMountainArray(int[] arr) {
        int max = 0, maxIndex = 0;
        for(int i = 0; i < arr.length; i++){
            if(max < arr[i]){
                max = arr[i];
                maxIndex = i;
            }
        }
        if(maxIndex == 0 || maxIndex == arr.length-1)return false;
        for(int left = 1; left < maxIndex; left++){
            if(arr[left] <= arr[left-1])return false;
        }
        for(int right = arr.length-1; right>maxIndex; right--){
            if(arr[right]>=arr[right-1])return false;
        }
        return true;
    }
}