Okuzeka
Software Engineering vocabulary · Data Structures and Algorithms

Binary search

Meaning in software engineering, with examples

nounCommon term

In software engineering, binary search means: A fast way to find a value in a sorted list by checking the middle item and repeatedly throwing away the half where the value cannot be.

In Turkish: ikili arama

How it is used

Its time complexity is O(log n), so even a million items need only about 20 steps. It only works on sorted data. The same idea is behind 'git bisect', which finds the commit that introduced a bug.

Example sentences

  1. Since the timestamps are already sorted, we can use binary search instead of scanning the whole list.

  2. I did a binary search through the commits and found the one that broke the build.

Common collocations

  • implement binary search
  • binary search tree
  • O(log n)
  • git bisect
  • algorithmA clear, step-by-step method for solving a problem or doing a task, such as sorting a list or finding the shortest route between two points.
  • sortTo put items in a particular order, for example numbers from smallest to largest or names alphabetically. Many algorithms exist to do this efficiently.
  • time complexityHow the number of steps an algorithm takes grows as the size of its input grows, usually written in Big O notation.
  • Big O notationA way of describing how the running time or memory use of an algorithm grows as the input gets bigger, for example O(1), O(n) or O(n²).

More terms: Data Structures and Algorithms

Practise with graded reading

Reading at the right level is the fastest way to make new words stick. Pick free English books by level: