# BINARY SEARCH RECURSIVE & ITERATIVE IMPLEMENTATION – SHOUT CODERS 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.

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))

## 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

.

## 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 may have missed 