Improving the linear search technique?
up vote
-3
down vote
favorite
I'm afraid we have a bit of a sadistic instructor on our hand, because I honestly did not understand this question and never found the answer in the text book, nor searching the internet.
"2. If the list is already in sorted order, how can you utilize this information in improving the linear search technique? Show your improvement in the algorithm of linear search."
As far as I know, Linear Search have only one job, which is examining each element sequentially. HOW can it be improved? What I know is the Linear Search Big-O notation is O(n) and that O(n) is the worse case performance since the element is placed the very last in the list or array. I was about to answer that question by switching to binary search but then I found that binary search would take even longer since it'll take n/2 times to locate, n/4, n/8 and do on and linear search would take as much time.
Let me know if I'm getting this question the wrong way or I'm missing something about this. Appreciate your help.
java
asked 2 days ago
user9578589
14
|
show 8 more comments
up vote
-3
down vote
favorite
I'm afraid we have a bit of a sadistic instructor on our hand, because I honestly did not understand this question and never found the answer in the text book, nor searching the internet.
"2. If the list is already in sorted order, how can you utilize this information in improving the linear search technique? Show your improvement in the algorithm of linear search."
As far as I know, Linear Search have only one job, which is examining each element sequentially. HOW can it be improved? What I know is the Linear Search Big-O notation is O(n) and that O(n) is the worse case performance since the element is placed the very last in the list or array. I was about to answer that question by switching to binary search but then I found that binary search would take even longer since it'll take n/2 times to locate, n/4, n/8 and do on and linear search would take as much time.
Let me know if I'm getting this question the wrong way or I'm missing something about this. Appreciate your help.
java
asked 2 days ago
user9578589
14
1
You can choose a different starting point
– leonardkraemer
2 days ago
If it is a linked list then locating the middle element really needs O(n/2). For anArrayListit would be just O(1)
– Michael Butscher
2 days ago
I did, and as I said above, Binary search would be slower for slower for sorted list.
– user9578589
2 days ago
2
You have to specify the data-structure that you are searching in and all other factors, otherwise trying to optimize is pointless.
– leonardkraemer
2 days ago
A math question: is the list numerical and is it bound by the range of integers? That is to say, there is a clever math approach that can be taken if the values you're sorting against are known to be numerical only (e.g. no lexicographical strings or decimals) which can be used to optimize the approach.
– Makoto
2 days ago
|
show 8 more comments
up vote
-3
down vote
favorite
up vote
-3
down vote
favorite
I'm afraid we have a bit of a sadistic instructor on our hand, because I honestly did not understand this question and never found the answer in the text book, nor searching the internet.
"2. If the list is already in sorted order, how can you utilize this information in improving the linear search technique? Show your improvement in the algorithm of linear search."
As far as I know, Linear Search have only one job, which is examining each element sequentially. HOW can it be improved? What I know is the Linear Search Big-O notation is O(n) and that O(n) is the worse case performance since the element is placed the very last in the list or array. I was about to answer that question by switching to binary search but then I found that binary search would take even longer since it'll take n/2 times to locate, n/4, n/8 and do on and linear search would take as much time.
Let me know if I'm getting this question the wrong way or I'm missing something about this. Appreciate your help.
java
asked 2 days ago
user9578589
14
I'm afraid we have a bit of a sadistic instructor on our hand, because I honestly did not understand this question and never found the answer in the text book, nor searching the internet.
"2. If the list is already in sorted order, how can you utilize this information in improving the linear search technique? Show your improvement in the algorithm of linear search."
As far as I know, Linear Search have only one job, which is examining each element sequentially. HOW can it be improved? What I know is the Linear Search Big-O notation is O(n) and that O(n) is the worse case performance since the element is placed the very last in the list or array. I was about to answer that question by switching to binary search but then I found that binary search would take even longer since it'll take n/2 times to locate, n/4, n/8 and do on and linear search would take as much time.
Let me know if I'm getting this question the wrong way or I'm missing something about this. Appreciate your help.
java
java
asked 2 days ago
user9578589
14
asked 2 days ago
user9578589
14
asked 2 days ago
user9578589
14
asked 2 days ago
user9578589
14
asked 2 days ago
user9578589
14
14
1
You can choose a different starting point
– leonardkraemer
2 days ago
If it is a linked list then locating the middle element really needs O(n/2). For anArrayListit would be just O(1)
– Michael Butscher
2 days ago
I did, and as I said above, Binary search would be slower for slower for sorted list.
– user9578589
2 days ago
2
You have to specify the data-structure that you are searching in and all other factors, otherwise trying to optimize is pointless.
– leonardkraemer
2 days ago
A math question: is the list numerical and is it bound by the range of integers? That is to say, there is a clever math approach that can be taken if the values you're sorting against are known to be numerical only (e.g. no lexicographical strings or decimals) which can be used to optimize the approach.
– Makoto
2 days ago
|
show 8 more comments
1
You can choose a different starting point
– leonardkraemer
2 days ago
If it is a linked list then locating the middle element really needs O(n/2). For anArrayListit would be just O(1)
– Michael Butscher
2 days ago
I did, and as I said above, Binary search would be slower for slower for sorted list.
– user9578589
2 days ago
2
You have to specify the data-structure that you are searching in and all other factors, otherwise trying to optimize is pointless.
– leonardkraemer
2 days ago
A math question: is the list numerical and is it bound by the range of integers? That is to say, there is a clever math approach that can be taken if the values you're sorting against are known to be numerical only (e.g. no lexicographical strings or decimals) which can be used to optimize the approach.
– Makoto
2 days ago
1
1
You can choose a different starting point
– leonardkraemer
2 days ago
You can choose a different starting point
– leonardkraemer
2 days ago
If it is a linked list then locating the middle element really needs O(n/2). For an
ArrayList it would be just O(1)– Michael Butscher
2 days ago
If it is a linked list then locating the middle element really needs O(n/2). For an
ArrayList it would be just O(1)– Michael Butscher
2 days ago
I did, and as I said above, Binary search would be slower for slower for sorted list.
– user9578589
2 days ago
I did, and as I said above, Binary search would be slower for slower for sorted list.
– user9578589
2 days ago
2
2
You have to specify the data-structure that you are searching in and all other factors, otherwise trying to optimize is pointless.
– leonardkraemer
2 days ago
You have to specify the data-structure that you are searching in and all other factors, otherwise trying to optimize is pointless.
– leonardkraemer
2 days ago
A math question: is the list numerical and is it bound by the range of integers? That is to say, there is a clever math approach that can be taken if the values you're sorting against are known to be numerical only (e.g. no lexicographical strings or decimals) which can be used to optimize the approach.
– Makoto
2 days ago
A math question: is the list numerical and is it bound by the range of integers? That is to say, there is a clever math approach that can be taken if the values you're sorting against are known to be numerical only (e.g. no lexicographical strings or decimals) which can be used to optimize the approach.
– Makoto
2 days ago
|
show 8 more comments
1 Answer
1
active
oldest
votes
up vote
3
down vote
I found that binary search would take even longer since it'll take n/2 times to locate, n/4, n/8 and do on and linear search would take as much time.
It depends on whether List::get(int) is O(1) operation or an O(N) operation. That depends on the list class.
For a
LinkedListit isO(N). Callingget(i)has to follow the linksitimes starting from the head of the list.For an
ArrayListit isO(1). Callingget(i)is just anarray[i]operation on the list's element array.
Redo your calculations for binary search with the assumption that get is O(1) and (if your analysis is correct, and your understanding of binary search is correct) you should get O(logN) for lookup by value using binary search.
(But yes, binary search on a linked list is not an optimization relative to linear search. It would be O(N^2) - an anti-optimization, given that linear search is O(N).)
I'm afraid we have a bit of a sadistic instructor on our hand.
Possibly. An alternative explanation is that the instructor is trying to encourage you to improve your analytical thinking skills by getting you to work things out for yourself. That includes figuring out your mistakes, including possibly incorrect assumptions you are making. Sometimes, the best way to learn from a fundamental mistake is "the hard way".
answered 2 days ago
Stephen C
508k69554905
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
I found that binary search would take even longer since it'll take n/2 times to locate, n/4, n/8 and do on and linear search would take as much time.
It depends on whether List::get(int) is O(1) operation or an O(N) operation. That depends on the list class.
For a
LinkedListit isO(N). Callingget(i)has to follow the linksitimes starting from the head of the list.For an
ArrayListit isO(1). Callingget(i)is just anarray[i]operation on the list's element array.
Redo your calculations for binary search with the assumption that get is O(1) and (if your analysis is correct, and your understanding of binary search is correct) you should get O(logN) for lookup by value using binary search.
(But yes, binary search on a linked list is not an optimization relative to linear search. It would be O(N^2) - an anti-optimization, given that linear search is O(N).)
I'm afraid we have a bit of a sadistic instructor on our hand.
Possibly. An alternative explanation is that the instructor is trying to encourage you to improve your analytical thinking skills by getting you to work things out for yourself. That includes figuring out your mistakes, including possibly incorrect assumptions you are making. Sometimes, the best way to learn from a fundamental mistake is "the hard way".
answered 2 days ago
Stephen C
508k69554905
add a comment |
up vote
3
down vote
I found that binary search would take even longer since it'll take n/2 times to locate, n/4, n/8 and do on and linear search would take as much time.
It depends on whether List::get(int) is O(1) operation or an O(N) operation. That depends on the list class.
For a
LinkedListit isO(N). Callingget(i)has to follow the linksitimes starting from the head of the list.For an
ArrayListit isO(1). Callingget(i)is just anarray[i]operation on the list's element array.
Redo your calculations for binary search with the assumption that get is O(1) and (if your analysis is correct, and your understanding of binary search is correct) you should get O(logN) for lookup by value using binary search.
(But yes, binary search on a linked list is not an optimization relative to linear search. It would be O(N^2) - an anti-optimization, given that linear search is O(N).)
I'm afraid we have a bit of a sadistic instructor on our hand.
Possibly. An alternative explanation is that the instructor is trying to encourage you to improve your analytical thinking skills by getting you to work things out for yourself. That includes figuring out your mistakes, including possibly incorrect assumptions you are making. Sometimes, the best way to learn from a fundamental mistake is "the hard way".
answered 2 days ago
Stephen C
508k69554905
add a comment |
up vote
3
down vote
up vote
3
down vote
I found that binary search would take even longer since it'll take n/2 times to locate, n/4, n/8 and do on and linear search would take as much time.
It depends on whether List::get(int) is O(1) operation or an O(N) operation. That depends on the list class.
For a
LinkedListit isO(N). Callingget(i)has to follow the linksitimes starting from the head of the list.For an
ArrayListit isO(1). Callingget(i)is just anarray[i]operation on the list's element array.
Redo your calculations for binary search with the assumption that get is O(1) and (if your analysis is correct, and your understanding of binary search is correct) you should get O(logN) for lookup by value using binary search.
(But yes, binary search on a linked list is not an optimization relative to linear search. It would be O(N^2) - an anti-optimization, given that linear search is O(N).)
I'm afraid we have a bit of a sadistic instructor on our hand.
Possibly. An alternative explanation is that the instructor is trying to encourage you to improve your analytical thinking skills by getting you to work things out for yourself. That includes figuring out your mistakes, including possibly incorrect assumptions you are making. Sometimes, the best way to learn from a fundamental mistake is "the hard way".
answered 2 days ago
Stephen C
508k69554905
I found that binary search would take even longer since it'll take n/2 times to locate, n/4, n/8 and do on and linear search would take as much time.
It depends on whether List::get(int) is O(1) operation or an O(N) operation. That depends on the list class.
For a
LinkedListit isO(N). Callingget(i)has to follow the linksitimes starting from the head of the list.For an
ArrayListit isO(1). Callingget(i)is just anarray[i]operation on the list's element array.
Redo your calculations for binary search with the assumption that get is O(1) and (if your analysis is correct, and your understanding of binary search is correct) you should get O(logN) for lookup by value using binary search.
(But yes, binary search on a linked list is not an optimization relative to linear search. It would be O(N^2) - an anti-optimization, given that linear search is O(N).)
I'm afraid we have a bit of a sadistic instructor on our hand.
Possibly. An alternative explanation is that the instructor is trying to encourage you to improve your analytical thinking skills by getting you to work things out for yourself. That includes figuring out your mistakes, including possibly incorrect assumptions you are making. Sometimes, the best way to learn from a fundamental mistake is "the hard way".
answered 2 days ago
Stephen C
508k69554905
edited 1 hour ago
answered 2 days ago
Stephen C
508k69554905
answered 2 days ago
Stephen C
508k69554905
answered 2 days ago
Stephen C
508k69554905
508k69554905
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53402668%2fimproving-the-linear-search-technique%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
You can choose a different starting point
– leonardkraemer
2 days ago
If it is a linked list then locating the middle element really needs O(n/2). For an
ArrayListit would be just O(1)– Michael Butscher
2 days ago
I did, and as I said above, Binary search would be slower for slower for sorted list.
– user9578589
2 days ago
2
You have to specify the data-structure that you are searching in and all other factors, otherwise trying to optimize is pointless.
– leonardkraemer
2 days ago
A math question: is the list numerical and is it bound by the range of integers? That is to say, there is a clever math approach that can be taken if the values you're sorting against are known to be numerical only (e.g. no lexicographical strings or decimals) which can be used to optimize the approach.
– Makoto
2 days ago