Skip to content

Latest commit

 

History

History
63 lines (42 loc) · 2.37 KB

binary-search.html.markdown

File metadata and controls

63 lines (42 loc) · 2.37 KB
Raw
category name contributors
Algorithms & Data Structures
Binary Search

Binary Search

Why Binary Search?

Searching is one of the prime problems in the domain of Computer Science.Today there are more than 1 trillion searches per year, and we need algorithms that can do that very fastly. Binary search is one of the fundamental algorithms in computer science. In order to explore it, we’ll first build up a theoretical backbone, then use that to implement the algorithm properly.

Introduction

A simple approach to implement search is to do a linear search, but this approach takes a lot of time and this time grows linearly with the amount or number of data points. i.e., start from the leftmost element of arr[] and one by one compare x with each element of arr[], if x matches with an element, return the index. If x doesn’t match with any of elements, return -1.

Linear Search: O (n)               Linear Time

Binary Search: O ( log(n) )		   Logarithmic Time
def search(arr, x):
 
    for i in range(len(arr)):
 
        if arr[i] == x:
            return i
 
    return -1

Binary Search Algorithm

The basic requirement for binary search to work is that the data to search should be sorted (in any order).

Algo

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Logn). We basically ignore half of the elements just after one comparison.
1) Compare x with the middle element.
2) If x matches with middle element, we return the mid index.
3) Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4) Else (x is smaller) recur for the left half.
Following is Recursive implementation of Binary Search.

Ending Notes

There is another form of binary search that is very useful.

Books

Online Resources