> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/algorithms/binary-search]
> [project group:: neetcode 150]
> [difficulty:: ]
> [status:: done]
> [link:: https://leetcode.com/problems/binary-search/]
> [up:: [[Leetcode MOC]]]
## Problem
Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`.
You must write an algorithm with `O(log n)` runtime complexity.
**Example 1:**
**Input:** nums = [-1,0,3,5,9,12], target = 9
**Output:** 4
**Explanation:** 9 exists in nums and its index is 4
**Example 2:**
**Input:** nums = [-1,0,3,5,9,12], target = 2
**Output:** -1
**Explanation:** 2 does not exist in nums so return -1
**Constraints:**
- `1 <= nums.length <= 10^4`
- `-10^4 < nums[i], target < 10^4`
- All the integers in `nums` are **unique**.
- `nums` is sorted in ascending order.
## Solution
### Mine
#### Python
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0, r = len(nums) - 1
r = len(nums) - 1
while r - l > 1: # this is a sucky condition to use, because we want to check for when r == l too
m = (r + l) // 2
if nums[m] == target:
return m
elif nums[m] < target:
l = m # d'oh! we don't want to include the old midpoint!
else:
r = m
return -1
```
#### Rust
### LC's
## Things I Learned
## Scratchpad
A sorted list of numbers is a clue to use binary search.
Idea is to get the index that is the midpoint of the list, then if that's not the target, search the part of the list that would contain the target. This should be easy with recursion, but I'm hitting maximum recursion depth. I think I'm just forgetting how to return an unchanged number from a chain of recursive calls.
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
half_idx = len(nums) // 2
# if nums[half_idx] == target:
# return half_idx
if nums[half_idx] < target:
self.search(nums=nums[half_idx:], target=target)
elif nums[half_idx] > target:
self.search(nums=nums[:half_idx], target=target)
else:
return half_idx
```
### Neetcode Video
Have two pointers at each end of list. Find midpoint: $\frac{r + l}{m}$. Then if that midpoint doesn't have the value, update L or R as appropriate. This sidesteps recursion completely.
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] > target:
r = m - 1
elif nums[m] < target:
l = m + 1
else:
return m
return -1
```