[**Binary search**] is an efficient search algorithm based on the **divide and conquer strategy**. It **utilizes the ordered nature of the data to reduce the search range by half each time**, until the target element is found or the search range is empty.

Important

❓ Given an array `nums`

of length n, with elements arranged in ascending order and no duplicate elements. Please **find and return the index of the element target in the array**. If the array does not contain the element, return -1.

First, initialize the pointers i=0 and j=n-1, pointing to the first and last elements of the array, representing the search range [0, n-1]. The square brackets indicate a closed interval, which includes the boundary values themselves.

Next, perform the following two steps in a loop:

- Calculate the midpoint index $m = \lfloor {(i + j) / 2} \rfloor$, where $\lfloor : \rfloor$ represents the floor operation.
- Compare
`nums[m]`

and`target`

, and consider the following three cases:- If
`nums[m] < target`

, it means`target`

is in the range [m+1, j], so set i=m+1. - If
`nums[m] > target`

, it means`target`

is in the range [i, m-1], so set j=m-1. - If
`nums[m] = target`

, it means the target is found, so return the index m.

- If

If the array does not contain the target element, the search range will eventually shrink to empty. In this case, return -1.

It is worth noting that since i and j are of type `int`

, i+j may exceed the range of the `int`

type. To avoid integer overflow, the formula $m = \lfloor {i + (j - i) / 2} \rfloor$ is commonly used to calculate the midpoint.

```
/* Binary Search (closed interval) */
int BinarySearch(int[] nums, int target) {
// Initialize the closed interval [0, n-1], where i and j point to the first and last elements of the array
int i = 0, j = nums.Length - 1;
// Loop until the search range is empty (when i > j)
while (i <= j) {
int m = i + (j - i) / 2; // Calculate the midpoint index m
if (nums[m] < target) // This case indicates that the target is in the range [m+1, j]
i = m + 1;
else if (nums[m] > target) // This case indicates that the target is in the range [i, m-1]
j = m - 1;
else // The target element is found, return its index
return m;
}
// The target element is not found, return -1
return -1;
}
```

**Advantages**: It has good performance in terms of time and space.

**Limitations**:

- It is only suitable for
**ordered data**. If the input data is unordered, it is not worth sorting the data specifically for binary search. - It is only suitable for
**arrays**(contiguous storage space). - For
**small data sets, linear search performs better**. In algorithm problems,**linear search is often replaced by hash search to reduce the time complexity of the algorithm**.- Linear search: trading time for space
- Hash search: trading space for time

Binary search insertion point: Binary search can not only be used to search for target elements, but also has many variations, such as **searching for the insertion position of a target element**.

- Finding the left boundary
- Finding the right boundary

**Linear search** is suitable for **small or frequently updated data**;

**Binary search** is suitable for **large, sorted data**;

**Hash search** is suitable for **data that requires high query efficiency and does not require range queries**;

**Tree search** is suitable for **large dynamic data that needs to maintain order and support range queries**.