Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Binary Search: Implementation and Example

Description

This lecture covers the binary search algorithm, which efficiently finds an element in a sorted list by dividing the search interval in half. The instructor explains the algorithm's implementation and provides a step-by-step example using a sorted list of numbers.

Official source

Ontological neighbourhood

Theoretical computer science

Algorithms and data structures: Analysis of algorithms

Related concepts (20)

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.

Binary search algorithm

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

Binary search tree

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree. Binary search trees allow binary search for fast lookup, addition, and removal of data items.

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: Simple implementation: Jon Bentley shows a three-line C/C++ version that is five lines when optimized. Efficient for (quite) small data sets, much like other quadratic (i.e.

Related lectures (40)

Recursion and Binary Search

Introduces recursion and binary search algorithms for efficient problem-solving.

Binary Search Algorithm

Explains the binary search algorithm using two pointers to efficiently search a sorted list.

Complexity & Induction: Algorithms & Proofs

Explores worst-case complexity, mathematical induction, and algorithms like binary search and insertion sort.

Algorithms: Summary of the week

Covers algorithms for searching, sorting, optimization, and the Halting Problem.

Dynamic Programming: Palindromic Subsequences