Qualcomm Interview Question
Software Engineer / Developers<pre lang="java" line="1" title="CodeMonkey57905" class="run-this">public class binarySearch {
public int binarySrchRCR(int array[],int low,int high,int target){
int range = high - low;
int center = (range/2)+low;
if(range < 0){
System.out.println("Incorrect high and low");
} else if(range == 0 && array[low] != target){
System.out.println("Target not in array");
}
if(target == array[center]){
System.out.println("Target Found : "+array[center]);
return target;
}
else if(target < array[center])
return binarySrchRCR(array,low,center -1,target);
else
return binarySrchRCR(array,center+1,high,target);
}
}
</pre><pre title="CodeMonkey57905" input="yes">
</pre>
- Pretty straight forward, given a sorted array find if an element exists using binary search. Complexity: O(logn)
- Find pivot = (left+right)/2, check if data == Arr[pivot], if yes return 1
- else if data<Arr[pivot], search in left half recursively
- if bigger search in right half recursively
- do till left>right
Output: Found 22
- dnair89 March 12, 2012