Explain binary searching, Fibinocci search.
- 5 Answers
- 22846 Views
- CTS, IBM, TCS, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / nipesh.....janghel....bca..2nd
Binary Search
The binary search is the standard method for searching
through a sorted array. It is
much more efficient than a linear search, where we pass
through the array elements in
turn until the target is found. It does require that the
elements be in order.
The binary search repeatedly divides the array in two, each
time restricting the search to
the half that should contain the target element.
In this example, we search for the integer 5 in the 10-
element array below:
2 : 5 : 6 : 8 : 10 : 12 : 15 : 18 : 20 : 21
Loop 1 - Look at whole array
Low index = 0, high index = 9
Choose element with index (0+9)/2 = 4
Compare value (10) to target
10 is greater than 5, so the target must be in the lower
half of the array
Set high index = (4-1) = 3
Loop 2
Low index = 0, high index = 3
Choose element with index (0+3)/2 = 1
Compare value (5) to target
5 is equal to target
Target was found, index = 1
| Is This Answer Correct ? | 23 Yes | 4 No |
Answer / kamal.r
Searching a binary tree for a value that matches a key value
is FAST, especially for tightly packed trees (a tightly
packed tree contains about twice as many elements as the
previous level)
o Therefore at most log(2)n comparisons are required either
to find a match or determine that no match exists.
o For example, searching a tightly packed 1000-element
binary search tree requies at most 10 comparisons because 2
o a binary search tree with n elements has a minimum of
log(2)n levels
o in-order: 0. if parameter node is null then return; 1.
recursive traverse left subtrees entirely 2. display data 3.
recursive traverse right subtrees entirely
o pre-order: 0 if param node is null return 1. display data
2. recursive traverse left subtrees entirely 3. recursive
traverse right subtree entirely.
o post-order: 0 if param node is null then return; 1.
recursive traverse left subtrees entirely 2. recursive
traverse right subtree entirely 3. display data
o to keep it efficient you must make sure to keep tree
balanced. Best way is to ensure the inputted data is coming
in with random values...If they are sorted in
ascending/descending order the tree will definitely become
unbanlanced
Fibnacci search
The Fibonacci Sequence is defined such that the first two
numbers of
the sequence are 0 and 1. subesequent numbers are the sum of the
previous two. e.g.
0, 1, 1, 2, 3, 5, 8, 13 ......
| Is This Answer Correct ? | 18 Yes | 5 No |
Hey guys its fibonacci search not fibonacci sequence.
Its is efficient when locality of reference is plays a
greater role.
Go here:
http://en.wikipedia.org/wiki/Fibonacci_search_technique
| Is This Answer Correct ? | 10 Yes | 6 No |
Answer / bharath
finally a sensible answer.........
fibonacci search is based on fibonacci heaps.
it is advanced structure tugher to implement and even more
efficient than BSTs , latest kernels used it fr app handles...
| Is This Answer Correct ? | 2 Yes | 2 No |
Answer / saroj kumar satapathy
In case of fibonacii search, themain difference is that we
neednot the division of no of element in an array. Because
the febonacii element is the addition of previous two
numbers.
| Is This Answer Correct ? | 1 Yes | 1 No |
If we try to add duplicate key to the hashmap, what will happen?
What are linked lists good for?
What is data structure and its types?
What is the prerequisite for binary searching?
What do you mean by back edge?
Write a program to reverse a single linked list.
I am given a sequential algorithm that does a routine search on an unordered list. N = 20. The probability that the value x does NOT appear in the list is exactly 60%, and the probability that x DOES appear is 40%. The 3 questions that I could not get were: A) What is the avg number of element comparisons performed when n = 20 and x does NOT appear in the List. (my answer was 20, is this correct?) B) What is the avg number of element comparisons peformed when n = 20 and x DOES appear in the list? C) What is the avg number of element comparisons performed when n = 20. This should be a single number answer they said.
Explain implementation of traversal of a binary tree.
What is a Queue? Explain its operation with example?
What does the dummy header in linked list contain?
In what areas do data structures are applied?
What is data structure? Explain.
Windows 
