Binary Search

Binary Search Algorithm

Binary search algorithm finds a given element in a list of elements with O(log n) time complexity where n is total number of elements in the list. The binary search algorithm can be used with only a sorted list of elements. That means the binary search is used only with a list of elements that are already arranged in an order. The binary search can not be used for a list of elements arranged in random order. This search process starts comparing the search element with the middle element in the list. If both are matched, then the result is "element found". Otherwise, we check whether the search element is smaller or larger than the middle element in the list. If the search element is smaller, then we repeat the same process for the left sub list of the middle element. If the search element is larger, then we repeat the same process for the right sub list of the middle element. We repeat this process until we find the search element in the list or until we left with a sub list of only one element. And if that element also doesn't match with the search element, then the result is "Element not found in the list".

Binary search is implemented using following steps...

  • Step 1 - Read the search element from the user.
  • Step 2 - Find the middle element in the sorted list.
  • Step 3 - Compare the search element with the middle element in the sorted list.
  • Step 4 - If both are matched, then display "Given element is found!!!" and terminate the function.
  • Step 5 - If both are not matched, then check whether the search element is smaller or larger than the middle element.
  • Step 6 - If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left sub list of the middle element.
  • Step 7 - If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right sub list of the middle element.
  • Step 8 - Repeat the same process until we find the search element in the list or until sub list contains only one element.
  • Step 9 - If that element also doesn't match with the search element, then display "Element is not found in the list!!!" and terminate the function.

Algorithm

1.Input an array A of n elements and “data” to be sorted.

2. LB = 0,UB = n-1; mid = int (( LB + UB ) / 2 )

3. Repeat step 4 and 5 while ( LB <= UB ) and ( A [ mid ] != data )

4. If ( data <A [ mid ] )

            UB = mid - 1

    else

            LB = mid +1

5.Mid = int (( LB + UB ) / 2 )

6.If (A [ mid ] == data )

             Print “the data is found”

   else

             Print “the data is not found"

7. Exit

Complexity

S.No.

Performance

Complexity

1

Worst case

O(log n)

2

Best case

O(1)

3

Average Case

O(log n)

4

Worst case space complexity

O(1)

Example

Consider the following list of elements and the element to be searched...



Popular posts from this blog

DATA STRUCTURES-II

 UNIT – I  Tree: Header nodes, Threads, Binary search trees, Searching, Insertion and deletion in aBinary search tree , AVL search trees, Insertion and deletion in AVL search tree , m-waysearch tree, Searching, Insertion and deletion in an m-way search tree , B-trees, Searching,Insertion and deletion in a B-tree, B+tree , Huffman’s algorithm , General trees.  UNIT – II  Graphs: Warshall’s algorithm for shortest path , Dijkstra algorithm for shortest path , Operations on graphs , Traversal of graph , Topological sorting .  UNIT – III  Sorting: Internal & external sorting , Radix sort , Quick sort , Heap sort , Merge sort . Searching: Liner search, binary search, merging , Comparison of various sorting and searching algorithms on the basis of their complexity .  UNIT – IV  Files: Physical storage devices and their characteristics , Attributes of a file viz fields, records,Fixed and variable length records, Primary and secondary keys , Classification of files, File operations,
Read more

DATA STRUCTURES FOR B.TECH

DATA STRUCTURES Unit 1: Introduction :   Basic Terminologies:   C oncept of Data Structure, Choice of right Data Structure , Algorithms , how to design and develop algorithm, Complexity of algorithm.   Operations: insertion, deletion, traversal etc,   Analysis of an Algorithm. Searching:  Linear Search and Binary Search Techniques and their complexity analysis. Unit 2: Stacks  and  Queues : Stack  and  its  operations: Algorithms and their complexity analysis, Applications of Stacks: Expression       Conversion and evaluation -corresponding algorithms and complexity analysis. queue, Types of Queue: Simple  Queue, Circular Queue, Priority Queue ; Operations on each types of Queues: Algorithms and their analysis.   Unit 3 : Linked Lists:      Singly   linked  lists: Representation in memory, Algorithms of several operations:  Traversing, Searching, Insertion into, Deletion from linked list; Linked representation of Stack and Queue, Header nodes, Doubly linked list: operations on
Read more

DATA STRUCTURES FOR BCA

UNIT – I  Introduction: Elementary data organization, Data Structure definition , Data type vs. data structure , Categories of data structures, Data structure operations, Applications of data structures, Algorithms complexity and time-space tradeoff, Big-O notataion.   Strings: Introduction, Storing strings, String operations, Pattern matching algorithms.  UNIT – II  Arrays: Introduction, Linear arrays, Representation of linear array in memory, address calculations, Traversal, Insertions, Deletion in an array, Multidimensional arrays, Parallel arrays, Sparse arrays.  Linked List: Introduction, Array vs. linked list, Representation of linked lists in memory, Traversal, Insertion, Deletion, Searching in a linked list, Header linked list, Circular linked list, Two-way linked list, Threaded lists, Garbage collection, Applications of linked lists.  UNIT – III  Stack: Introduction, Array and linked representation of stacks, Operations on stacks, Applications of stacks: Polish notat
Read more