Binary search
class BinarySearch {
List data
// You may assume for this exercise that the input data is sorted in ascending order.
BinarySearch(List data) {
this.data = data
}
List<Integer> getSlice(int start, int end){
start = Math.max(0,start);
end = Math.min(this.data.size(), end);
return this.data.subList(start, end);
}
int indexOf(item) {
int halfLength;
int index = this.data.indexOf(item);
if(this.data.size() % 2 ==0){
halfLength = this.data.size()/2;
while(this.data.size()>0){
if(this.data.get(halfLength-1)==item) return index;
else if (this.data.get(halfLength-1) > item){
this.data = getSlice(0, halfLength-1);
}
else if (!this.data.get(halfLength-1).equals(item)){
this.data = getSlice(halfLength-1, this.data.size());
if(this.data.get(halfLength-1).equals(item)) {
index += (halfLength-1);
return index;
}
else indexOf(item);}
}
}
else {
halfLength= this.data.size()/2+1;
if(this.data.get(halfLength-1) == item) return index;
else if (this.data.get(halfLength-1) > item){
this.data = getSlice(0, halfLength-1);
}
else if (this.data.get(halfLength-1) < item){
this.data = getSlice(halfLength-1, this.data.size());
}
}
return index;
}
}
Thank you, friend!
I'm @steem.history, who is steem witness.
Thank you for witnessvoting for me.
please click it!
(Go to https://steemit.com/~witnesses and type fbslo at the bottom of the page)
The weight is reduced because of the lack of Voting Power. If you vote for me as a witness, you can get my little vote.