이진탐색을 활용하는 여러가지 경우 구현

이진 탐색

이진탐색이란 중복 값이 없는 정렬된 배열에서 원하는 값을 찾는 효율적인 알고리즘이다.

 

핵심 로직

1. 배열의 중앙값을 구한다.
2. 중앙값과 찾고자 하는 값(target)과 비교한다.
   1. 중앙값 < target 인 경우 : 시작점을 중앙값의 +1 값으로 선택 ( 중앙 기준 왼쪽을 버린다.)
   2. 중앙값 > target 인 경우 : 끝점을 중앙값의 -1 값으로 선택 (중앙 기준 오른쪽을 버린다.)

 

배열에 있는 값의 인덱스 찾기

public static int search(int[] temp, int target) {
  int start = 0;
  int end = temp.length - 1;
  int result = -1;

  while(start <= end) {
      int mid = (start + end) / 2;
      if (temp[mid] < target) {
          start = mid + 1;
      } else if (temp[mid] > target){
          end = mid - 1;
      } else {
          return mid;
      }
  }

  return result;
}

 

target 보다 크거나 같은 인덱스 찾기

public static int searchGreaterOrEqualIndex(int[] temp, int target) {
    int start = 0;
    int end = temp.length - 1;

    while(start <= end) {
        int mid = (start + end) / 2;
        if (temp[mid] < target) {
            start = mid + 1;
        } else if (temp[mid] > target){
            end = mid - 1;
        } else {
            return mid;
        }
    }

    return start;
}

 

target 보다 작거나 같은 인덱스 찾기

public static int searchSmallerOrEqualIndex(int[] temp, int target) {
    int start = 0;
    int end = temp.length - 1;

    while(start <= end) {
        int mid = (start + end) / 2;
        if (temp[mid] < target) {
            start = mid + 1;
        } else if (temp[mid] > target){
            end = mid - 1;
        } else {
            return mid;
        }
    }

    return end;
}

 

중복이 있는 배열에서 target과 같은 첫 번째 인덱스 찾기

public static int searchDuplicateFirstIndex(int[] temp, int target) {
    int start = 0;
    int end = temp.length - 1;
    int result = -1;

    while(start <= end) {
        int mid = (start + end) / 2;
        if (temp[mid] < target) {
            start = mid + 1;
        } else {
            result = mid;
            end = mid - 1;
        }
      }
return result;
}

 

중복이 있는 배열에서 target과 같은 마지막 인덱스 찾기

public static int searchDuplicateLastIndex(int[] temp, int target) {
		int start = 0;
		int end = temp.length - 1;
		int result = -1;
		
		while(start <= end) {
		    int mid = (start + end) / 2;
		    if(temp[mid] <= target) {
		        start = mid + 1;
		    } else {
		        result = mid;
		        end = mid - 1;
		    }
		}
		return result-1;
}

 

전체 코드

public class binarySearch {

    public static void main(String[] args) {
        int[] array = {1, 2, 4, 6, 9, 13};
        System.out.println(search(array, 4));           // 2
        System.out.println(searchGreaterOrEqualIndex(array, 7)); // 4
        System.out.println(searchSmallerOrEqualIndex(array, 7));  // 3

        int[] duplicateArray = {1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5};
        System.out.println(searchDuplicateFirstIndex(duplicateArray, 3));  // 5
        System.out.println(searchDuplicateLastIndex(duplicateArray, 3));   // 7
    }

    public static int search(int[] temp, int target) {
        int start = 0;
        int end = temp.length - 1;
        int result = -1;

        while(start <= end) {
            int mid = (start + end) / 2;
            if (temp[mid] < target) {
                start = mid + 1;
            } else if (temp[mid] > target){
                end = mid - 1;
            } else {
                return mid;
            }
        }

        return result;
    }

    public static int searchGreaterOrEqualIndex(int[] temp, int target) {
        int start = 0;
        int end = temp.length - 1;

        while(start <= end) {
            int mid = (start + end) / 2;
            if (temp[mid] < target) {
                start = mid + 1;
            } else if (temp[mid] > target){
                end = mid - 1;
            } else {
                return mid;
            }
        }

        return start;
    }

    public static int searchSmallerOrEqualIndex(int[] temp, int target) {
        int start = 0;
        int end = temp.length - 1;

        while(start <= end) {
            int mid = (start + end) / 2;
            if (temp[mid] < target) {
                start = mid + 1;
            } else if (temp[mid] > target){
                end = mid - 1;
            } else {
                return mid;
            }
        }

        return end;
    }
    public static int searchDuplicateFirstIndex(int[] temp, int target) {
        int start = 0;
        int end = temp.length - 1;
        int result = -1;

        while(start <= end) {
            int mid = (start + end) / 2;
            if (temp[mid] < target) {
                start = mid + 1;
            } else {
                result = mid;
                end = mid - 1;
            }
        }
        return result;
    }

    public static int searchDuplicateLastIndex(int[] temp, int target) {
        int start = 0;
        int end = temp.length - 1;
        int result = -1;

        while(start <= end) {
            int mid = (start + end) / 2;
            if(temp[mid] <= target) {
                start = mid + 1;
            } else {
                result = mid;
                end = mid - 1;
            }
        }
        return result-1;
    }
}