## binary_search()


Search for a target value in a sorted list.


Usage


``` python
binary_search(
    arr,
    target,
)
```


Uses the binary search algorithm to find the index of `target` in the sorted list `arr`. Returns -1 if the target is not found.


## Parameters


`arr: list`  
A sorted list of integers to search.

`target: int`  
The integer value to search for.


## Returns


`int`  
The index of `target` in `arr`, or -1 if not found.


## Notes

The input list must be sorted in ascending order. If the list is not sorted, the result is undefined.

The time complexity is O(log n) and the space complexity is O(1).


## References

1.  <span style="font-weight: 600; color: #6c757d;">\[1\]</span> Knuth, D.E. (1998). "The Art of Computer Programming", Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, Section 6.2.1.


## Examples

``` python
>>> binary_search([1, 3, 5, 7, 9], 5)
```

2

``` python
>>> binary_search([1, 3, 5, 7, 9], 4)
```

-1