Search in a sorted array by using Binary search

binary search

Introduction

Binary Search algorithm is an efficient searching algorithm which allows you to search for an item in a sorted array. Another simple approach to search a value in an array is Linear search, but the time complexity of linear search is O(n) whereas we can achieve the result by using binary search in O(log n) time.

Problem Statement

Given a list of elements and a value to be searched. Find the index of the value, if present otherwise return -1.

Input : 
arr[] = {5, 8, 9, 12, 15, 18}
k = 8

Output : 
2 (index of the k)

Let’s try to understand how binary search works using a real world example.

Example

The process we use to search for a word in a dictionary is same as that of binary search algorithm. In the dictionary, all the words are sorted alphabetically.

So, if we want to search for the word which starts with the letter “B” Binary.

  1. We open the dictionary randomly and check if the current page is showing words which are greater than or less than B.  
  2. If the page opened has a word greater than B, we normally flip to the left side, otherwise
  3. We flip to the right side and if the page contains the word we are looking for. Well we just got our answer.
  4. We need to repeat step 1-3, until the word is found.

In the same way we implement binary search. Let’s see the implementation.

Algorithm

Similarly in binary search, we follow the following steps-

  1. Take two pointers : low and high.
  2. Initialize low = 0 and high = n-1, where n is number of elements in the given array.
  3. Repeatedly divide the sorted array into half by finding the middle element using the formula –
    mid = low + (high - low)/2
  4. We then start comparing the middle value k.
  5. If the value at the mid is less than k, then we move to right side, or
  6. If the value at the mid is greater than k, then we move to left side.
  7. Repeat steps 3-5, till we find the target value.
  8. Once the value is found, return the index position, else return -1.

This algorithm reduces the number of iterations to half as compared to the linear search algorithm.

Visualization of the algorithm

Implementation of the algorithm

Let’s see how this algorithm works

Upper bound of the running time complexity of the program is O(log n).


Thank you for reading 🙂

Leave a Reply