Algorithm for finding a key by binary search technique, Data Structure & Algorithms

Assignment Help:

Q. Write down an algorithm for finding a key from a sorted list using the binary search technique or method.

Ans.

Binary Search Algorithm is written below

1. if (low > high)

2. return (-1)

3. mid = (low +high)/2;

4 .if ( X = = a [mid])

5 return (mid);

6 if ( X < a [mid])

7 search for X in a (low) to [mid -1];

8 else

9 search for X in a [mid + 1] to a [high];

Related Discussions:- Algorithm for finding a key by binary search technique

Example of telephone directory, A telephone directory having n = 10 records...

A telephone directory having n = 10 records and Name field as key. Let us assume that the names are stored in array 'm' i.e. m(0) to m(9) and the search has to be made for name "X"

The complexity of searching an element, The complexity of searching an elem...

The complexity of searching an element from a set of n elements using Binary search algorithm is O(log n)

Operations on sequential files, Insertion: Records has to be inserted at t...

Insertion: Records has to be inserted at the place dictated by the sequence of keys. As is obvious, direct insertions into the main data file would lead to frequent rebuilding of

Data structures, 1. You are required to hand in both a hard copy and an el...

1. You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn. 2. You

Hash clash, Q. What do you understand by the term by hash clash? Explain in...

Q. What do you understand by the term by hash clash? Explain in detail any one method to resolve the hash collisions.

Four applications or implementation of the stack, Q. Write down any four ap...

Q. Write down any four applications or implementation of the stack. Ans. (i) The Conversion of infix to postfix form (ii)

Demonstrate that dijkstra''s algorithm, Demonstrate that Dijkstra's algorit...

Demonstrate that Dijkstra's algorithm does not necessarily work if some of the costs are negative by finding a digraph with negative costs (but no negative cost dicircuits) for whi

Algorithm of binary search, Step 1: Declare array 'k' of size 'n' i.e. k(n)...

Step 1: Declare array 'k' of size 'n' i.e. k(n) is an array which stores all the keys of a file containing 'n' records Step 2: i←0 Step 3: low←0, high←n-1 Step 4: while (l

Frequency count, i:=1 while(i { x:=x+1; i:=i+1; }

i:=1 while(i { x:=x+1; i:=i+1; }

Non-recursive implementation of binary tree traversals, As we have seen, as...

As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive me

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages