Поиск элементов в отсортированном массиве со свойствами между диапазоном?

Question

У меня есть массив класса Obj, отсортированный по возрастанию в зависимости от возраста. Мне нужно найти количество предметов Obj, возраст которых в пределах заданного минимального и максимального возраста в массиве в O (log (N)).

Я не думаю, что могу использовать binarySearch, потому что .equals верно только тогда, когда имя и возраст одинаковы.

Это то, что я сделал до сих пор, но я не уверен, в чем сложность.

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

Напишите компаратор и отсортируйте массив, используя компаратор.

Затем используйте вторую двоичную поисковую подпись, которая принимает компаратор с вашим новым компаратором, чтобы найти верхнюю и нижнюю границы.

Если вы не получили точное соответствие, вы получите отрицательное число, это указывает, где будет ваше значение, если оно найдено, инвертируйте это, и у вас есть место начала/конца значений, которые у вас есть, которые встречаются ваши граничные условия.

Answer 2

Этот вопрос такой же, как и для here, где я дал O (logn).

Идея заключается в бинарном поиске по нижней границе и верхней границе. Для вашего примера, все значения говорят о возраст значение.