BINARY SEARCH RECURSIVE & ITERATIVE IMPLEMENTATION – SHOUT CODERS

5 Likes Comment
BinarySRCH

At beginning we perform Linear search program to search a given element. It sequentially checks each element of the array until it gets the desired value. There are another approach i.e. DIVIDE AND CONQUER algorithmic approach. In this approach, A given large array is first divided into two smaller sub arrays and then recursively operate the sub-arrays. But It only consider one half of that array. In this way, operating time is reduced. At each step we found the mid value and compares it with target value. There are three cases possible –
Case 1: if target = A[mid] , we return mid

Case 2: If target < A[mid], we consider left division

Case 3: If target > A[mid], we consider right division
We repeat the process until target is found or array space is exhausted.

GENERAL ALGORITHM:

Step 1: [INITIALIZE] SET BEG = lower_bound
        END = upper_bound, POS = – 1
    Step 2: Repeat Steps 3 and 4 while BEG <=END
    Step 3: SET MID = (BEG + END)/2
    Step 4: IF A[MID] = VAL
        SET POS = MID
        PRINT POS
        Go to Step 6
        ELSE IF A[MID] > VAL
        SET END = MID – 1
        ELSE
        SET BEG = MID + 1
        [END OF IF]
        [END OF LOOP]
    Step 5: IF POS = -1
        PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
        [END OF IF]
    Step 6: EXIT

RECURSIVE ALGORITHM:

1: Initialize array size as N

  1. Initialize Array as arr and searching element as x
  2. Set low=0 and high=N-1
  3. set index= binsrch with arr, low, high, and x variable.
  4. if index==-1 then Element not found otherwise, found .

binsrch(arr, low, high, x):

  1. if low> high then return -1 as element is not found.
  2. set mid= low + (high-low)/2;
  3. check arr[mid] is equal to x if true return mid
  4. else if if arr[mid] > x then return (binsrch(arr, low, mod-1 ,x))
  5. else return (binsrch(arr, mod+1, high ,x))

RECURSIVE JAVA PROGRAM:

RECURSIVE PYTHON PROGRAM:

ITERATIVE ALGORITHM :

1. Initialize array size as N

  1. Initialize Array as arr and searching element as x
  2. Set low=0 and high=N-1
  3. while low > high go to step 10
  4. set mid=low+(high-low) / 2
  5. check arr[mid] is equal to x if true return mid
  6. if arr[mid] > x then set high = mid-1
  7. if arr[mid] < x then set low = mid+1
  8. go to step 4
  9. return -1 element not found.

ITERATIVE C PROGRAM:

ITERATIVE JAVA PROGRAM:

ITERATIVE PYTHON PROGRAM:

.

INPUT/OUTPUT:

How many element: 5

Enter value: 1

Enter value: 2

Enter value: 3

Enter value: 4

Enter value: 5

All value Entered

Enter the item which you want to search 3

Item found at location 3

.

Binary search program time complexity is O(log n). It discarded half of the array every time within loop. It is a quick guide of binary search. Another searching algorithm Linear Search. Check this out.

You might like

Saif

About the Author: Saif

Leave a Reply

Your email address will not be published. Required fields are marked *

Close Bitnami banner
Bitnami