Given a sorted array and a value k, write a program to find whether that number is present in that array or not.
The first solution that comes to the mind for this problem is to traverse through the entire array and find whether it is having the value k and return true or false. This takes O(n) running time. But then, we are presented with a hint that the input array is sorted (lets assume in ascending order). This problem can be attacked by doing a divide and rule analysis.
This can be done recursively. See whether k is inbetween the last and first element in the array. If it is, then divide the array into two and repeat the same. If its not, simply return false. Yes, its as simple as that. Following is the java code for the same.
The first solution that comes to the mind for this problem is to traverse through the entire array and find whether it is having the value k and return true or false. This takes O(n) running time. But then, we are presented with a hint that the input array is sorted (lets assume in ascending order). This problem can be attacked by doing a divide and rule analysis.
This can be done recursively. See whether k is inbetween the last and first element in the array. If it is, then divide the array into two and repeat the same. If its not, simply return false. Yes, its as simple as that. Following is the java code for the same.
Leave some comments if you have anything to say.
Cheers!
Braga
6 comments:
Isn't this just a regular binary search? Sorry if I'm missing something...
@Pin-Sho Feng : What do you mean by binary search ?
There is something called as binary search tree where you will first have to construct a BST which will take time more than O(n). Once its constructed, you can find the value in O(log n) time,
But that is a different ballgame in this scenario. You will have to find k with least possible time which implicitly says you cannot waste any time at all.
Hope I was clear. Let me know if you have any questions.
By binary search I mean this:
http://en.wikipedia.org/wiki/Binary_search_algorithm
In this case, an iterative version would be faster (in Java at least), avoiding some recursion overhead.
@Pin-Sho Feng : Got it. Appreciate the link ! And yeah iteration and recursion always have trade off in terms of clarity, overhead and ease of understanding.
Thanks for stopping by!
this is coded very similar to a binary search function.
@Faz - you are right.. good observation
Post a Comment