My Question is simple from the below code how do you implement an algorithm that will search the same occurence of items after the mid value is found? Assuming the data is sorted.
I would appreciate you guys help me implementing based on my code below. I have approaches such as adding an extra function such as an exponential search but I am afraid that will ruin the time complexity of the algorithm.
I would like you guys to implement an algorithm that looks for multiple same items and count their occurrence as well as it will allows the time complexity of the code below remains as O(LOG N)
private boolean binarySearchComparator(TYPE key) {
int low = 0;
int high = count - 1;
while (low <= high) {
int mid = (low + high) / 2;
TYPE midVal = list[mid];
int cmp = comparator.compare(midVal, key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return true;
}
}
My Full Codes here Take a look.
Sorted List Interface
public interface SortedListInterface <TYPE extends Comparable<TYPE>> {
public boolean add(TYPE element);
public TYPE get(int index);
public int search(TYPE element);
public TYPE remove(int index);
public void clear();
public int getLength();
public boolean isEmpty();
public boolean isFull();
}
SearchComparator Class
public class MobileSearch implements Comparator<Student>{
private String type;
public void setType(String type) {
this.type = type;
}
public String getType() {
return type;
}
@Override
public int compare(Student student1, Student student2) {
int result = 0;
if(this.type.equals("mobile")){
result = student1.getMobileNo().compareTo(student2.getMobileNo());
System.out.print(result+"mobile");
}
else if(this.type.equals("name")){
result = student1.getName().getFullName().compareTo(student2.getName().getFullName());
System.out.println(result+"name");
}
else if(this.type.equals("group")){
result = student1.getGroup().compareTo(student2.getGroup());
System.out.print(result+"group");
}
return result;
}
}
SortedArrayList Implementation
public class SortedArrayList<TYPE extends Comparable<TYPE>> implements SortedListInterface<TYPE>{
//Data Types
private TYPE[] list;
private int length;
private static final int SIZE = 10;
private Comparator<? super TYPE> comparator;
private int count;
@SuppressWarnings("unchecked")
public SortedArrayList(Comparator<? super TYPE> c) {
comparator = c;
list = (TYPE[]) new Comparable[SIZE]; // No way to verify that 'list' only contains instances of 'T'.
/* NOTE: Following is not allowed.
list = new T[SIZE]; // Cannot create a generic array of T
*/
}
// Constructors
public SortedArrayList() {
this(SIZE);
}
public SortedArrayList(int size) {
length = 0;
list = (TYPE[]) new Comparable[SIZE]; // an array of instances of a class implementing Comparable interface and able to use compareto method but its overidden instead
}
// Setter & Getters
@Override
public int getLength() {
return length;
}
@Override
public boolean isEmpty() {
return length == 0;
}
@Override
public boolean isFull() {
return false;
}
@Override
public void clear() {
length = 0;
}
// Array Expansion
private boolean isArrayFull() {
return length == list.length;
}
private void expandArray() {
TYPE[] oldList = list;
int oldSize = oldList.length;
list = (TYPE[]) new Object[2 * oldSize];
for (int i = 0; i < oldSize; i++) // copy old array elements into new array elements
list[i] = oldList[i];
}
// ADT METHODs
// Add New Elements Function
@Override
// public boolean add(TYPE element) {
// int i = 0;
//
// while (i < length && element.compareTo(list[i]) > 0) // return 0 with equal , return more than 1 if element larger than list[i] , return -1 if less
// {
// i++;
// }
//
// makeRoom(i + 1);
// list[i] = element;
// length++;
// return true;
// }
public boolean add(TYPE element) {
boolean result = false;
if (count == 0) {
list[0] = element;
count = 1;
result = true;
}
else {
if (!isFull()) {
int i = 0;
while (list[i] != null) {
if (element.compareTo(list[i]) < 0) {
break;
}
i++;
}
if (list[i] != null) {
for (int j = count - 1; j >= i; j--) {
list[j + 1] = list[j];
}
}
list[i] = element;
count++;
result = true;
}
}
return result;
}
private void makeRoom(int index) { // accepts given index
int newIndex = index - 1;
int lastIndex = length - 1;
for (int i = lastIndex; i >= newIndex; i--)
list[i + 1] = list[i];
}
//Remove Elements Function
@Override
public TYPE remove(int index) { // accepts given index
TYPE result = null;
if ( index >= 1 && index <= length ) {
result = list[index - 1];
if (index < length)
removeGap(index);
length--;
}
return result;
}
private void removeGap(int index) { // accepts given index and remove the gap where the element its removed
int removedIndex = index - 1;
int lastIndex = length - 1;
for (int i = removedIndex; i < lastIndex; i++)
list[i] = list[i + 1]; // shifts elements back to remove the gap
}
// Get Element
@Override
public TYPE get(int index) { // accepts given index and return the object
TYPE object = null;
if ( index >= 1 && index <= length)
object = list[index - 1];
return object;
}
// Search Algorithms
@Override
// public boolean search(TYPE element) {
// boolean found = false;
//
// int lo = 0;
// int hi = count - 1;
//
// while (lo <= hi) {
// int mid = (lo + hi) / 2;
// if (list[mid].compareTo(element) < 0) {
// lo = mid + 1;
// }
// else if (list[mid].compareTo(element) > 0) {
// hi = mid - 1;
// }
// else if (list[mid].compareTo(element) == 0) {
// found = true;
// break;
// }
// return found
// }
public int search(TYPE element) {
return exponentialSearch(element);
}
private boolean binarySearchComparable(TYPE element) {
boolean found = false;
int lo = 0;
int hi = count - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (list[mid].compareTo(element) < 0) {
lo = mid + 1;
}
else if (list[mid].compareTo(element) > 0) {
hi = mid - 1;
}
else if (list[mid].compareTo(element) == 0) {
found = true;
break;
}
}
System.out.print("Single");
return found;
}
private int exponentialSearch(TYPE key){
int ind = binarySearchComparator(key);
// If element is not present
if (ind == -1)
return -1;
// Count elements on left side.
int count = 1;
int left = ind - 1;
int i = 1;
while (left >= 0 && (comparator.compare(list[left], key)) == 0)
{
// lol[i] = list[left];
System.out.println(left+"lefttest");
i++;
count++;
left--;
}
// Count elements
// on right side.
int right = ind + 1;
try{
while (right < list.length && (comparator.compare(list[right], key)) == 0)
{
System.out.println(right+"righttest");
// lol[i] = arr[right];
i++;
count++;
right++;
}
}catch(Exception e){
}
return count;
}
private int binarySearchComparator(TYPE key) {
int low = 0;
int high = count - 1;
while (low <= high) {
int mid = (low + high) / 2 ;
TYPE midVal = list[mid];
int cmp = comparator.compare(midVal, key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -1; // key not found.
}
//To String Method
@Override
public String toString() {
String result = "";
for (int i = 0; i < count; i++)
result += list[i] + "\n";
return result;
}
}
Name Class
public class Name {
// Data Types
private String firstName;
private String lastName;
// Constructors
public Name() {
}
public Name(String firstName, String lastName) {
this.firstName = firstName;
this.lastName = lastName;
}
// setter
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public void setLastName(String lastName) {
this.lastName = lastName;
}
// getter
public String getFirstName() {
return firstName;
}
public String getLastName() {
return lastName;
}
public String getFullName(){
return firstName + " " + lastName;
}
@Override
public String toString() {
return "Name{" + "firstName=" + firstName + ", lastName=" + lastName + '}';
}
}
Student Class
public class Student implements Comparable<Student>{
// Data Types
private String studID;
private Name name;
private String gender;
private String icNo;
private String mobileNo;
private Course course;
private String group;
private String dOB;
// Constructors
public Student() {
}
public Student(String studID, Name name, String gender, String icNo, String mobileNo, Course course, String group, String dOB) {
this.studID = studID;
this.name = name;
this.gender = gender;
this.icNo = icNo;
this.mobileNo = mobileNo;
this.course = course;
this.group = group;
this.dOB = dOB;
}
public Student(Name name) {
this.name = name;
}
// setter
public void setStudID(String studID) {
this.studID = studID;
}
public void setName(Name name) {
this.name = name;
}
public void setGender(String gender) {
this.gender = gender;
}
public void setIcNo(String icNo) {
this.icNo = icNo;
}
public void setMobileNo(String mobileNo) {
this.mobileNo = mobileNo;
}
public void setCourse(Course course) {
this.course = course;
}
public void setGroup(String group) {
this.group = group;
}
public void setdOB(String dOB) {
this.dOB = dOB;
}
// getter
public String getStudID() {
return studID;
}
public Name getName() {
return name;
}
public String getGender() {
return gender;
}
public String getIcNo() {
return icNo;
}
public String getMobileNo() {
return mobileNo;
}
public Course getCourse() {
return course;
}
public String getGroup() {
return group;
}
public String getdOB() {
return dOB;
}
@Override
public String toString() {
return "Student{" + "name=" + name + ", gender=" + gender + ", icNo=" + icNo + ", mobileNo=" + mobileNo + ", course=" + course + ", group=" + group + ", dOB=" + dOB + '}';
}
@Override
public int compareTo(Student object) { // Sort according to name if name same then sort according to gender and so on.
int c = this.name.getFullName().compareTo(object.getName().getFullName());
if(c == 0)
c = this.gender.compareTo(object.getGender());
if(c == 0)
c = this.icNo.compareTo(object.getIcNo());
if(c == 0)
c = this.mobileNo.compareTo(object.getMobileNo());
if(c == 0)
c = this.group.compareTo(object.getGroup());
if(c == 0)
c = this.dOB.compareTo(object.getdOB());
return c;
}
public static Student[] sort(Student[] object,String category){
Student[] array;
if(category.equals("ID")){
for (int i=1; i < object.length; i++) {
for(int j = 0 ; j < object.length - i ; j++)
if( (object[j].getGender().compareTo(object[j+1].getGender())) > 0 ){
Student lol = object[j];
object[j] = object[j+1];
object[j+1] = lol;
}
}
}
array = object;
return array;
}
}
Course Class
public class Course {
// Data Types
private String courseCode;
private String courseName;
private double courseFee;
// Constructors
public Course() {
}
public Course(String courseCode, String courseName, double courseFee) {
this.courseCode = courseCode;
this.courseName = courseName;
this.courseFee = courseFee;
}
// setter
public void setCourseCode(String courseCode) {
this.courseCode = courseCode;
}
public void setCourseName(String courseName) {
this.courseName = courseName;
}
public void setCourseFee(double courseFee) {
this.courseFee = courseFee;
}
// getter
public String getCourseCode() {
return courseCode;
}
public String getCourseName() {
return courseName;
}
public double getCourseFee() {
return courseFee;
}
@Override
public String toString() {
return "CourseCode = " + courseCode + "Course Name = " + courseName + "Course Fee = " + courseFee;
}
}
