Binary search is important. The idea is simple.

But you wouldn’t believe how incredibly useful it would be.

**Basic Abstractions**

Name | Summary |
---|---|

What are the arrays to be examined? | |

How to divide them into half? | |

Check the middle and how to drop one half? |

**Code Skeleton**

Name | Example |
---|---|

Clarifications: whether array is sorted? | |

Clarifications: whether array allow duplicates? | |

How to initialize? | left, right := 0, len(l)-1 VS left, right := 0, len(l) |

How to check, drop? | target -> middle vs middle -> target |

How to move? | left = mid, left = mid+1, left = mid-1 |

When to break? | left<right: adjacent, left<=right: overlap |

What break means? | |

Any corner case? |

**Top Questions**

See all binarysearch problems: #binarysearch.

- Review: Binary Search Problems
- LintCode: Single Number IV
- LintCode: Leftmost One
- LintCode: Count Negative Number
- Leetcode: Valid Perfect Square
- Leetcode: Time Based Key-Value Store
- Leetcode: Sqrt(x)
- Leetcode: Single Element in a Sorted Array
- Leetcode: Search Insert Position
- Leetcode: Search in Rotated Sorted Array II

See more blog posts.