Clinic #11 - Binary Search

Pattern: Binary Search (the invariant) · LC 704

Ye board dikhata hai ek sorted list ko baar-baar beech se kaatte jaana - har compare pe aadhi list hamesha ke liye phenk di jaati hai, jab tak ek hi ghar na bache.

Before you start. Tumhe bas itna pata hona chahiye ki sorted array kya hai: chhote se bade number tak lagi hui ek list. Ye idea Foundations #01 - Complexity (Big-O ka poora naksha) mein “har baar aadha karo” wale idea ke roop mein already dikh chuka hai (engineers use O(log n) kehte hain: list double ho, toh bas ek step aur) - is lesson mein wahi idea poora, kaam karta code ban jaata hai.