범위 사이의 속성을 사용하여 정렬 된 배열에서 항목을 찾으십니까?

Question

나이 필드를 기준으로 오름차순으로 정렬 된 Obj 클래스의 배열이 있습니다. O (log (N)) 시간에 배열의 주어진 최소 및 최대 나이 내에 나이가있는 Obj 항목의 수를 찾아야합니다.

.equals는 이름과 나이가 같을 때만 true이기 때문에 binarySearch를 사용할 수 있다고는 생각하지 않습니다.

이것은 내가 지금까지 해 온 것입니다. 그러나 나는 그 복잡성이 무엇인지 잘 모릅니다.

public class Obj { 
    private String name; 
    private int age; 

    private Obj(String name, int age) { 
     if (name == null) { 
      throw new IllegalArgumentException(); 
     } 
     this.name = name; 
     this.age = age; 
    } 

    public String getName() { 
     return name; 
    } 

    public int getAge() { 
     return age; 
    } 

    public boolean equals(Object o) { 
     if (!(o instanceof Obj)) { 
      return false; 
     } 

     Obj other = (Obj) o; 
     return name.equals(other.getName()) && age == other.getAge(); 
    } 

    public static Obj[] loadFromFile(File f) { 
     // Loads from file and returns an array of Obj 
    } 
} 

public static int getObjCountInRange(Obj[] a, int minAge, int maxAge) { 
    if(a == null || (minAge < 0 || maxAge < 0) || (minAge > maxAge)) { 
     throw new IllegalArgumentException(); 
    } 

    int start = 0; 
    for(int i = 0; i < a.length; i++) { 
     if(a[i].getAge() >= minAge) { 
      start = i; 
      break; 
     } 
    } 

    int end = 0; 
    for(int i = a.length -1; i > 0; i--) { 
     if(a[i].getAge() <= maxAge) { 
      end = i; 
      break; 
     } 
    } 

    return (end - start) + 1; 
} 

Answer 1

비교기를 작성하고 비교기를 사용하여 정렬하십시오.

그런 다음 새로운 Comparator를 사용하여 비교기를 사용하여 상한 및 하한을 찾는 두 번째 이진 검색 서명을 사용하십시오.

정확하게 일치하지 않는 경우 음수가 표시됩니다.이 값은 발견 된 값의 위치와 반전되며 사용자가 가지고있는 값의 시작/끝 위치를 나타냅니다 경계 조건.

Answer 2

이 질문은 O (로그인) 구현을 준 here과 동일합니다.

아이디어는 하한값과 상한값에 대한 이진 검색 범위입니다. 귀하의 예를 들어, 모든 값은 년 값에 대해 이야기하고 있습니다.