ਬਾਈਨਰੀ ਸਰਚ ਕਿਵੇਂ ਕੰਮ ਕਰਦੀ ਹੈ, ਅਤੇ ਇਹ ਕੀ ਲੋੜ ਹੈ?

Question

Accepted Answer

**Binary search** ਇੱਕ **ਛਾਂਟੀ ਹੋਈ** ਐਰੇ ਵਿੱਚ ਇੱਕ ਟਾਰਗੇਟ ਨੂੰ ਖੋਜ ਲੱਭਦੀ ਹੈ ਅਤੇ ਸਰਚ ਰੇਂਜ ਨੂੰ ਵਾਰ ਵਾਰ ਅੱਧਾ ਕਰਦੀ ਹੈ। ਹਰੇਕ ਤੁਲਨਾ ਬਾਕੀ ਬਚੀਆਂ ਅੱਧੀ ਐਲੀਮੈਂਟਸ ਨੂੰ ਖਤਮ ਕਰਦੀ ਹੈ, ਜਿਸਦੇ ਨਤੀਜੇ ਵਜੋਂ **O(log n)** ਸਮਾਂ ਮਿਲਦਾ ਹੈ। ## ਵਿਚਾਰ ਮੱਧ ਐਲੀਮੈਂਟ ਨੂੰ ਦੇਖੋ। ਜੇ ਇਹ ਟਾਰਗੇਟ ਦੇ ਬਰਾਬਰ ਹੈ, ਫਿਰ ਮੁਕੰਮਲ। ਜੇ ਟਾਰਗੇਟ ਛੋਟਾ ਹੈ, ਤਾਂ ਖੱਬੀ ਅੱਧਾ ਖੋਜ ਕਰੋ; ਜੇ ਵੱਡਾ ਹੈ, ਤਾਂ ਸੱਜੀ ਅੱਧਾ ਖੋਜ ਕਰੋ। ਜਦੋਂ ਤੱਕ ਮਿਲ ਨਹੀਂ ਜਾਂ ਰੇਂਜ ਖਾਲੀ ਨਹੀਂ ਹੋ ਜਾਂਦੀ, ਦੁਹਰਾਓ। ## ਉਦਾਹਰਨ ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## ਟਰੇਸ ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## ਜਟਿਲਤਾ - **ਸਮਾਂ:** O(log n)। **ਸਪੇਸ:** O(1) ਦੁਹਰਾਓ। ## ਪਾਸੇ **ਇਨਪੁਟ ਛਾਂਟਿਆ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ** — ਨਹੀਂ ਤਾਂ ਨਤੀਜੇ ਬੇਮਤਲਬ ਹਨ। `lo`/`hi` ਵਿੱਚ off-by-one ਬਗਸ ਅਤੇ ਕਈ ਭਾਸ਼ਾਵਾਂ ਵਿੱਚ ਇੰਟੀਜਰ ਓਵਰਫਲੋ ਤੋਂ ਸਾਵਧਾਨ ਰਹੋ (`lo + (hi-lo)//2` ਵਰਤੋ)। ## ਇਹ ਕਿਉਂ ਮਾਇਨੇ ਰੱਖਦਾ ਹੈ ਸਰਚ ਸਪੇਸ ਨੂੰ ਅੱਧਾ ਕਰਨਾ ਇੱਕ ਮਿਲੀਅਨ-ਐਲੀਮੈਂਟ ਖੋਜ ਨੂੰ ~20 ਤੁਲਨਾਵਾਂ ਵਿੱਚ ਬਦਲ ਦਿੰਦਾ ਹੈ। Divide-and-conquer ਪੈਟਰਨ ਜੋ ਇਸਦੇ ਪਿੱਛੇ ਹੈ, ਰੁੱਖਾਂ, ਡੇਟਾਬੇਸਾਂ ਅਤੇ ਲਾਖਾਂ ਇੰਟਰਵਿਊ ਸਵਾਲਾਂ ਵਿੱਚ ਦੁਬਾਰਾ ਦਿਖਾਈ ਦਿੰਦਾ ਹੈ। ਇਸਦੀ ਇੱਕ ਸਖ਼ਤ ਲੋੜ — ਛਾਂਟਿਆ ਹੋਇਆ ਇਨਪੁਟ — ਜਾਣਨਾ ਤੁਹਾਨੂੰ ਇੱਕ ਵਿਲੱਖਣ ਸੂਖਮ ਬੱਗ ਤੋਂ ਬਚਾਉਂਦਾ ਹੈ।