Thank you for printing our content at www.domain-name.com. Please check back soon for new contents.
66%
Learn to code efficiently with DSA Learn with Programiz PRO (https://programiz.pro/course/dsa-with-python)
off
PRO (https://programiz.pro/course/dsa-with-python)
ProgramizSearch tutorials & examples
(/)
www.domain-name.com
Binary Search
Binary Search is a searching algorithm for finding an
element's position in a sorted array.
In this approach, the element is always searched in the
middle of a portion of an array.
Binary search can be implemented only on a sorted
list of items. If the elements are not sorted already,
we need to sort them first.
Binary Search Working
Binary Search Algorithm can be implemented in two ways
which are discussed below.
1. Iterative Method
2. Recursive Method
The recursive method follows the divide and conquer
(/dsa/divide-and-conquer) approach.
The general steps for both methods are discussed below.
1. The array in which searching is to be performed is:
Initial array
Let x = 4 be the element to be searched.
2. Set two pointers low and high at the lowest and the
highest positions respectively.
Thank you for printing our content at www.domain-name.com.
Setting pointers Please check back soon for new contents.
66% 3. Find
Learn to code efficiently withthe
DSAmiddle position
Learn with PROof the
mid
Programiz array ie. (https://programiz.pro/course/dsa-with-python)
off
mid = (low + high)/2 and arr[mid] = 6 .
PRO (https://programiz.pro/course/dsa-with-python)
ProgramizSearch tutorials & examples
(/)
www.domain-name.com
Mid element
4. If x == arr[mid] , then return mid . Else, compare the
element to be searched with arr[mid] .
5. If x > arr[mid] , compare x with the middle element
of the elements on the right side of arr[mid] . This is
done by setting low to low = mid + 1 .
6. Else, compare x with the middle element of the
elements on the left side of arr[mid] . This is done by
setting high to high = mid - 1 .
Finding mid element
7. Repeat steps 3 to 6 until low meets high .
Mid element
8. x = 4 is found.
Thank you for printing our content at www.domain-name.com.
Found Please check back soon for new contents.
66%
Learn to code efficiently with DSA Learn with Programiz PRO (https://programiz.pro/course/dsa-with-python)
off
PRO (https://programiz.pro/course/dsa-with-python)
ProgramizSearch tutorials & examples
Binary
(/) Search Algorithm
www.domain-name.com
Iteration Method
do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1
Recursive Method
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] // x is on the right
return binarySearch(arr, x, mid + 1, high)
else // x is on the
return binarySearch(arr, x, low, mid - 1)
Python, Java, C/C++ Examples
(Iterative Method)
Python Java C C++
# Binary Search in python
def binarySearch(array, x, low, high):
# Repeat until the pointers low and high meet each o
while low <= high:
mid = low + (high - low)//2
if x == array[mid]:
return mid
elif x > array[mid]:
low = mid + 1
else:
high = mid - 1
return -1
array = [3, 4, 5, 6, 7, 8, 9]
x = 4
result = binarySearch(array, x, 0, len(array)-1)
if result != -1:
Python, Java, C/C++ Examples
Thank you for printing our content at www.domain-name.com. Please check back soon for new contents.
66% (Recursive Method)
Learn to code efficiently with DSA Learn with Programiz PRO (https://programiz.pro/course/dsa-with-python)
off
Python PRO Java
tutorialsC& examples
C++
(https://programiz.pro/course/dsa-with-python)
ProgramizSearch
(/)
www.domain-name.com
# Binary Search in python
def binarySearch(array, x, low, high):
if high >= low:
mid = low + (high - low)//2
# If found at mid, then return it
if x == array[mid]:
return mid
# Search the right half
elif x > array[mid]:
return binarySearch(array, x, mid + 1, high)
# Search the left half
else:
return binarySearch(array, x, low, mid - 1)
else:
return -1
array = [3, 4, 5, 6, 7, 8, 9]
x = 4
Binary Search Complexity
Time Complexities
Best case complexity: O(1)
Average case complexity: O(log n)
Worst case complexity: O(log n)
Space Complexity
The space complexity of the binary search is O(1) .
Binary Search Applications
In libraries of Java, .Net, C++ STL
While
Thank you for printing our debugging,
content the binary searchPlease
at www.domain-name.com. is used to pinpoint
check back soon for new contents.
the place where the error happens.
66%
Learn to code efficiently with DSA Learn with Programiz PRO (https://programiz.pro/course/dsa-with-python)
off
PRO (https://programiz.pro/course/dsa-with-python)
ProgramizSearch tutorials & examples
(/)
www.domain-name.com
Next Tutorial:
(/dsa/greedy-algorithm)
Greedy Algorithm
Previous Tutorial:
(/dsa/linear-search)
Linear Search
Share on:
(https://www.facebook.com/sharer/sharer.php? (https://twitter.com/intent/tweet?
u=https://www.programiz.com/dsa/binary- text=Check%20this%20amazing%20article%20on%2
search) search)
Did you find this article helpful?
Our premium learning platform, created with
over a decade of experience.
Try Programiz PRO
(https://programiz.pro/)
Related Tutorials
DS & Algorithms
Linear Search
(/dsa/linear-search)
DS & Algorithms
Quicksort Algorithm
(/dsa/quick-sort)
DS & Algorithms
Insertion Sort Algorithm
Thank you for printing our content at www.domain-name.com. Please check back soon for new contents.
(/dsa/insertion-sort)
66%
Learn to code efficiently
DS &with DSA Learn with Programiz PRO
Algorithms (https://programiz.pro/course/dsa-with-python)
off
Binary Search Tree(BST)
PRO (https://programiz.pro/course/dsa-with-python)
ProgramizSearch tutorials & examples
(/)
www.domain-name.com
(/dsa/binary-search-tree)
