Comparing Arrays and LinkedList, we know it is easy for Array to access element(takes O(1)), but hard to insert or delete(takes O(n)), LinkedList is opposite, access element takes O(n), but deletion and insertion is easy(takes O(1)).
What about comparing elements and find a sepecfic elemnt in a sorted array?
Well, we can do linear search (O(n)). Loop through the elements in array and find out the value that is exact same as target value.
We can also use binary search: repeatedly dividing the search interval in harf to narrow down the search. Binary search only takes O(logn) time complexity.
Continue reading