# Binary Search

The aim is to find the index of an element in a **sorted** array. The input must be an array sorted in ascending order.

We search the sorted array by repeatedly dividing the search interval in half. We begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, we narrow the interval to the lower half. Otherwise, we narrow it to the upper half. We repeatedly check until the value is found or the interval is empty.

**Intuitive Example**: Searching for the name of a person in a list of names sorted in alphabetical order.

Binary Search can be solved in both a recursive and iterative manner:

**Python code for recursive Binary Search**:

```
def bin_search_recursive(a, k, l, h):
    mid = (l+h)//2
    if k==a[mid]:
        return mid
    elif k<a[mid]:
        return bin_search_recursive(a, k, l, mid-1)
    else:
        return bin_search_recursive(a, k, mid+1, h)

def bin_search_call(a, k):
    return bin_search_recursive(a, k, 0, len(a))

a = [int(x) for x in input("Enter array a: ").strip().split()]
k = int(input("Enter key k: "))
try:
    print("%d found at index %d" %(k, bin_search_call(a, k)))
except:
    print("Element not found!")
```

**Python code for iterative Binary Search**:

```
def bin_search_iterative(a, k):
    l = 0
    h = len(a) - 1

    while l<=h:
        mid = (l+h)//2
        if k==a[mid]:
            return mid
        elif k<a[mid]:
            h = mid-1
        else:
            l = mid+1

a = [int(x) for x in input("Enter array a: ").strip().split()]
k = int(input("Enter key k: "))
try:
    print("%d found at index %d" %(k, bin_search_iterative(a, k)))
except:
    print("Element not found!")
```

**Time complexity**: O(lg n)


---

# Agent Instructions: 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://vikram-bajaj.gitbook.io/cs-gy-6033-i-design-and-analysis-of-algorithms-1/main/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.