> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/divide_and_conquer/binary_search.md).

# Binary Search

## [Intro](http://youtu.be/cfCs7smUJbY?t=5m27s)

You have a phone book. Find Mike Smith. You can go through page by page from the beginning. You are guaranteed to find Mike Smith by this algorithm. But it's very naive. What if we start from the middle? Since the phone book is sorted, we can rip the phone book in half and throw away the part that does not contain Mike Smith. We are fundamentally left with the same problem, but it's only half the size. The powerful part of this idea is that a 1000 page phone book takes 10 tears and a 4 billion page phone book only takes 32 tears.

![](/files/-LtpqXIoBzg5lJxv1GmB)

## Algorithm

```
1. Set L to 0 and R to n − 1.
2. If L > R, the search terminates as unsuccessful.
3. Set m (the position of the middle element) to the floor (the largest previous integer) of (L + R) / 2.
4. If Am < T, set L to m + 1 and go to step 2.
5. If Am > T, set R to m – 1 and go to step 2.
6. Now Am = T, the search is done; return m.
```

The algorithm is trivial but the underlying idea "decrease and conquer" - pick half of the original problem - is fundamental. The algorithm is intuitively recursive. Since we only have one subproblem after each "divide", we can convert the recursion to a while loop to save some space on the call stack.

## Time Complexity

`T(n) = T(n/2) + 1` we can pick half of the original problem with O(1) work. This recurrence guarantees us O(logn) worst case runtime. If we can come up with an O(n) brute force solution and the interviewer asks can you do better, binary search is probably the right approach.

## Summary

The key conditions to perform a binary search is the following:

* a minimum (can be index, value, row, depends on what we want to search)
* a maximum
* a validator to check the midpoint so we can determine which half to keep

## Type of Questions

* Array problems (binary search on index)
  * Binary search (find target) on array
  * Decrease and conquer on array (pick half)
* Grid problems
  * Use a condition to eliminate half of the grid each turn
* Number problems (binary search on answers)
  * Binary search on the number line


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/divide_and_conquer/binary_search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.