1/3/26, 11:30 AM Binary Search with Python
❯
Tutorials References Exercises Certificates Search... Upgrade Get Certified Sign In
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Stacks
Queues
Linked Lists
Hash Tables
Trees
Binary Trees
Binary Search Trees
AVL Trees
Graphs
Linear Search
Binary Search
Bubble Sort
Selection Sort
Insertion Sort
Binary Search with Python
Quick Sort COLOR
❮ Previous Next ❯
Counting Sort PICKER
Radix Sort
Merge Sort
Binary Search
Python MySQL
MySQL Get Started The Binary Search algorithm searches through a sorted array and returns the index of the
value it searches for.
Search for value 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Run the simulation to see how the Binary Search algorithm works.
Binary Search is much faster than Linear Search, but requires a sorted array to work.
The Binary Search algorithm works by checking the value in the center of the array. If the
target value is lower, the next value to check is in the center of the left half of the array.
This way of searching means that the search area is always half of the previous search area,
and this is why the Binary Search algorithm is so fast.
This process of halving the search area happens until the target value is found, or until the
search area of the array is empty.
How it works:
1. Check the value in the center of the array.
2. If the target value is lower, search the left half of the array. If the target value is
higher, search the right half.
[Link] 1/5
1/3/26, 11:30 AM Binary Search with Python
3. Continue step 1 and 2 for the new reduced part of the array until the target value is ❯
Tutorials References Exercises Certificates
found or until the search area is empty.
Upgrade Get Certified Sign In
4. If the value is found, return the target value index. If the target value is not found,
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Stacks
return -1.
Queues
Linked Lists
Hash Tables
Trees
Binary Trees Manual Run Through
Binary Search Trees
AVL Trees Let's try to do the searching manually, just to get an even better understanding of how
Graphs Binary Search works before actually implementing it in a Python program. We will search
Linear Search for value 11.
Binary Search
Step 1: We start with an array.
Bubble Sort
Selection Sort
[ 2, 3, 7, 7, 11, 15, 25]
Insertion Sort
Quick Sort
Counting Sort
Step 2: The value in the middle of the array at index 3, is it equal to 11?
Radix Sort
Merge Sort [ 2, 3, 7, 7, 11, 15, 25]
Python MySQL
MySQL Get Started Step 3: 7 is less than 11, so we must search for 11 to the right of index 3. The values to the
right of index 3 are [ 11, 15, 25]. The next value to check is the middle value 15, at index 5.
[ 2, 3, 7, 7, 11, 15, 25]
Step 4: 15 is higher than 11, so we must search to the left of index 5. We have already
checked index 0-3, so index 4 is only value left to check.
[ 2, 3, 7, 7, 11, 15, 25]
We have found it!
Value 11 is found at index 4.
Returning index position 4.
Binary Search is finished.
Run the simulation below to see the steps above animated:
Search for value 11
[ 2, 3, 7, 7, 11, 15, 25 ]
Implementing Binary Search in Python
To implement the Binary Search algorithm we need:
1. An array with values to search through.
[Link] 2/5
1/3/26, 11:30 AM Binary Search with Python
2. A target value to search for. ❯
Tutorials References Exercises Certificates Upgrade
3. A loop that runs as long as left index is less than, or equal to, the right index.
Get Certified Sign In
4. An if-statement that compares the middle value with the target value, and returns
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Stacks
the index if the target value is found.
5. An if-statement that checks if the target value is less than, or larger than, the middle
Queues
value, and updates the "left" or "right" variables to narrow down the search area.
Linked Lists
6. After the loop, return -1, because at this point we know the target value has not
Hash Tables
been found.
Trees
Binary Trees The resulting code for Binary Search looks like this:
Binary Search Trees
AVL Trees
Graphs Example Get your own Python Server
Linear Search
Binary Search Create a Binary Search algorithm in Python:
Bubble Sort
def binarySearch(arr, targetVal):
Selection Sort
left = 0
Insertion Sort
right = len(arr) - 1
Quick Sort
Counting Sort while left <= right:
Radix Sort mid = (left + right) // 2
Merge Sort
if arr[mid] == targetVal:
return mid
Python MySQL
MySQL Get Started if arr[mid] < targetVal:
left = mid + 1
else:
right = mid - 1
return -1
mylist = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
x = 11
result = binarySearch(mylist, x)
if result != -1:
print("Found at index", result)
else:
print("Not found")
Run Example »
Binary Search Time Complexity
Each time Binary Search checks a new value to see if it is the target value, the search area
is halved.
This means that even in the worst case scenario where Binary Search cannot find the target
value, it still only needs log n comparisons to look through a sorted array of n values.
2
Time complexity for Binary Search is: O(log 2
n)
[Link] 3/5
1/3/26, 11:30 AM Binary Search with Python
❯
Tutorials References Exercises Certificates Upgrade Get Certified
Note: When writing time complexity using Big O notation we could also just have written
Sign In
HTML CSS JAVASCRIPT SQL , but O(log2JAVA
PYTHON
O(log n) n) reminds
PHPus that
HOWtheTO
array search
[Link] isC halved
C++for every
C# new
BOOTSTRAP REACT MYS
Stacks comparison, which is the basic concept of Binary Search, so we will just keep the base 2
Queues indication in this case.
Linked Lists
Hash Tables
Trees If we draw how much time Binary Search needs to find a value in an array of n values,
Binary Trees compared to Linear Search, we get this graph:
Binary Search Trees
AVL Trees
Graphs
Linear Search
Binary Search
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Counting Sort
Radix Sort
Merge Sort
Python MySQL
MySQL Get Started
❮ Previous Sign in to track progress Next ❯
-->
PLUS SPACES GET CERTIFIED FOR TEACHERS
FOR BUSINESS CONTACT US
Top Tutorials Top References
HTML Tutorial HTML Reference
CSS Tutorial CSS Reference
JavaScript Tutorial JavaScript Reference
How To Tutorial SQL Reference
SQL Tutorial Python Reference
Python Tutorial [Link] Reference
[Link] Tutorial Bootstrap Reference
Bootstrap Tutorial PHP Reference
PHP Tutorial HTML Colors
Java Tutorial Java Reference
[Link] 4/5
1/3/26, 11:30 AM Binary Search with Python
C++ Tutorial AngularJS Reference
❯
Tutorials jQuery Tutorial
References
Top Examples
Exercises Certificates jQuery Reference
Get Certified
Upgrade Get Certified Sign In
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
HTML Examples HTML Certificate
Stacks CSS Examples CSS Certificate
Queues JavaScript Examples JavaScript Certificate
How To Examples Front End Certificate
Linked Lists SQL Examples SQL Certificate
Python Examples Python Certificate
Hash Tables [Link] Examples PHP Certificate
Bootstrap Examples jQuery Certificate
Trees PHP Examples Java Certificate
Binary Trees Java Examples C++ Certificate
XML Examples C# Certificate
Binary Search Trees jQuery Examples XML Certificate
AVL Trees
Graphs
Linear Search
FORUM ABOUT ACADEMY
Binary Search
W3Schools is optimized for learning and training. Examples might be simplified to improve reading and learning.
Bubble Sort Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full correctness
of all content. While using W3Schools, you agree to have read and accepted our terms of use, cookies and privacy policy.
Selection Sort
Insertion Sort Copyright 1999-2026 by Refsnes Data. All Rights Reserved. W3Schools is Powered by [Link].
Quick Sort
Counting Sort
Radix Sort
Merge Sort
Python MySQL
MySQL Get Started
[Link] 5/5