Algorithm: Binary Search in Array

Binary search algorithm is enhancement in searching of element in array, It reduces worst case complexity of of linear search from O(n) to O(log₂n). In this algorithm all the elements in the array must be sorted.

BinarySearch(ArrayValues[], n, searchValue, LB, UB)

Here ArrayValues is an array of size n, Which is already sorted. In which we have to search an element searchValue. LB is lower bound and UB is an upper bound of the array. Mid is an intermediate variable which will contains middle element of array.

Step 1: till LB<=UB repeat step 2 and 3 

Step 2: Mid = (LB + UB)/2

Step 3: i) if ArrayValues[Mid] = searchValue then return Mid.

           ii) if ArrayValues[Mid] > searchValue then 

                       a) UB = Mid-1

               else

                      a)  LB = Mid+1

Step 4: return -1

Click here for Explanation

Scene 1

searchValue =   18; LB=0; UB=6

ArrayValues =>    15                18            19             21            25            28                 31            

Indexes                   0                  1               2              3              4              5                   6

1st Iteration:

Mid = (6+0) = 3; ArrayValues[Mid] = 21 => ArrayValues[Mid] > SearchValue

so LB = 0; UB = Mid - 1 = 2

2nd Iteration

Mid = (2+0) / 2 = 1; ArrayValues[Mid] = 18 = searchValue

Return 18

Scene 2

searchValue =   17; LB=0; UB=6

ArrayValues =>    15                18            19             21            25            28                 31            

Indexes                   0                  1               2              3              4              5                   6

1st Iteration:

Mid = (6+0) = 3; ArrayValues[Mid] = 21 => ArrayValues[Mid] > searchValue

so LB = 0; UB = Mid - 1 = 2

2nd Iteration

Mid = (2+0) / 2 = 1; ArrayValues[Mid] = 18 => ArrayValues[Mid] > searchValue

So LB = 0; UB = Mid-1 = 0

3rd Iteration

Mid = (0+0)/2) = 0; ArrayValues[Mid] = 15 => ArrayValues[Mid] < searchValue

So LB = Mid +1 = 1; UB = 0

4th Iteration

LB>UB [search failed]

return -1;