# Binary Search

If we have an <mark style="color:red;">**array**</mark> that is <mark style="color:red;">**sorted**</mark>, we can use a much more <mark style="color:red;">**efficient algorithm**</mark> called a <mark style="color:red;">**Binary Search**</mark>. In binary search <mark style="color:red;">**each time**</mark> we <mark style="color:red;">**divide array**</mark> into <mark style="color:red;">**two equal half**</mark> and <mark style="color:red;">**compare middle element**</mark> with <mark style="color:red;">**search element**</mark>.

#### Searching Logic

* If <mark style="color:red;">**middle element**</mark> is <mark style="color:red;">**equal to search element**</mark> then we got that element and <mark style="color:red;">**return that index**</mark>
* If <mark style="color:red;">**middle element**</mark> is <mark style="color:red;">**less than search element**</mark> we <mark style="color:red;">**look right part**</mark> of array
* If <mark style="color:red;">**middle element**</mark> is <mark style="color:red;">**greater than search element**</mark> we <mark style="color:red;">**look left part**</mark> of array.

### The complexity of Binary Search Technique

* **Time Complexity:** O(1) for the best case. O(log2 n) for average or worst case.
* **Space Complexity:** O(1)&#x20;

### Binary Search - Algorithm

![](/files/VWB1IFc77krkFmlaow50)

### Binary Search - Example

#### Search for <mark style="color:red;">**6**</mark> in given array

![](/files/A2EohrvpWo3mjPpLvbSG)

![](/files/sUrE89DoYDwzYAreTcgg)

![](/files/JfiuJ2RrNg0ECXouxJkP)

### Example:

```
#include<iostream>
using namespace std;

int binarySearch(int a[], int start, int end, int key) {
   if(start <= end) {
      int mid = (start + (end - start) /2); //mid location of the list
      if(a[mid] == key)
         return mid;
      if(a[mid] > key)
         return binarySearch(a, start, mid-1, key);
         return binarySearch(a, mid+1, end, key);
   }
   return -1;
}

int main() {
   int n, skey, loc;
   cout << "Enter number of items: ";
   cin >> n;

   int arr[n]; 
   cout << "Enter items: " << endl;

   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }

   cout << "Enter which element to search in the list: ";
   cin >> skey;

   if((loc = binarySearch(arr, 0, n, skey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}
```

### Output

```
Enter number of items: 10
Enter items:
-1 5 6 18 19 25 46 78 102 114
Enter which element to search in the list: 6
Item found at location: 2
```


---

# 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://fsm.gitbook.io/algo/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.