Algorithms and Flowchart Binary Search - Ishwaranand

News

Algorithms and Flowchart Binary Search

Binary Search

Q) Explain the binary search with an algorithm.

  • Binary search is an efficient search as compared to a linear search. it is used to search elements from a sorted array.
  • In the search middle element of an array is compared with the item, if they are equal then a search is successful.
  • Otherwise, it item > middle element then perform searching in the upper half or if item<middle element then perform searching in the lower half. 
binary search stl, binary search python, binary search java, binary search in c binary search geeksforgeeks, binary search program in c, binary search recursive, binary search time complexity, binary search example step by step, linear search, binary search javascript, binary search c++ stl, binary search - leetcode, binary search in c using recursion, binary search c#, time complexity of binary search tree, binary search vs linear search, interpolation search simulation, binary search stl, the binary search algorithm quizlet, binary search javascript khan academy, binary search competitive programming, binary search program in c++, data structures searching problems,
Image Source ~ Crafted With ©Ishwaranand - 2020 ~ Image by ©Ishwaranand

Working Binary Search

  • Initially set beg = 1 and end = size of the array, then find the middle of an array using mid= (beg+end)/2.
  • Compare array[mid] with the item to be searched, if they are equal the search is successful and the process is stopped.
  • When the value of item >  array[mid] then proceed to search in the upper half using beg = mid + 1. Otherwise, when the value of item < array [mid] then proceeds to search in the lower half using end = mid - 1.
  • The same steps are repeated in the respective half until the element is found or beg <= end.

Algorithm: Binary_Serach[Data[], lb, ub, item, loc]

  • This the algorithm for linear search
  • Data[]- Array of an element,
  • lb- lower bound,
  • ub - upper bound,
  • beg -beginning position,
  • end - end position,
  • mid - middle position,
  • item - element to be search,
  • loc - location.

step 1: start
step 2 : [initialize variable]
             Set beg=lb, end=ub,loc=0
step 3 :  Repeat steps4, 5 and 6 until beg <= end and data[mid] != item
step 4 :  [find middle]
              mid=(beg+end)/2
step 5 : [compare data[mid] and item]
             if data [mid] == itme the 
                 set loc=mid 
             End if
step 6 : [jump in respective half]
             if item >data[mid]then
                 beg = mid + 1
            else
                 end = mid - 1
step 7 : if loc == 0 then
                 Print "item is not found"
            else
                 Print "item is found at loc"
step 8 : Stop

Example Binary Search

Consider the following example containing 8sorted array elements.
12345678
1122334455667788
Element to be searched is: 55
set
beg = 1 and
end = 8

Pass 1
Find mid
mid = (ben+end)/2
mid = (1+8)/2
mid = 4
compare A[mid] with 55
12345678
1122334455667788
Red is mid
As A[mid] != 55 &
55 > A[mid] Proceed searching in the Upper half
Set beg = mid + 1
beg = 4 + 1
beg = 5

Pass 2
Find mid
mid = (beg+end)/2
mid = (5+8)/2
mid = 6
compare A[mid] with55
12345678
112233555667788
Red is mid
As A[mid] != 55 &
55 < A[mid] Proceed searching in the lower half
Set end = mid - 1
end = 6 - 1
end = 5
Pass 3
Find mid
mid = (beg+end)/2
mid = (5+5)/2
mid = 5
compareA[mid] with 55
12345678
1122334455667788
Red is mid
As A[mid] = 55
Print "Search is Successful"

Result: Given element 55 is found ar 5th  position. 

No comments

Comment on Ishwaranand or Happy Day
Not, Add any types of links