Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

🔥 个人主页：Blank Verse

Binary Search is an efficient search algorithm that is suitable for quickly locating target elements in an ordered array. Compared with linear search, the time complexity of binary search is O(log n), which is more efficient. This article will introduce the principle, implementation and application of binary search algorithm in detail.

---

1. Algorithm Principle

Binary search quickly locates the target element by continuously halving the search range. The basic steps are as follows:

1. Initialize the search range to the start and end index of the array.
2. Calculate the intermediate index.
3. Compares the element at the middle index to the target element.
   • If they are equal, the target element is found and its index is returned.
   • If the target element is smaller than the element at the middle index, the search is narrowed to the left half.
   • If the target element is greater than the element at the middle index, the search is narrowed to the right half.
4. Repeat the above steps until the search range is empty or the target element is found.

---

2. Algorithm Implementation

Here is a JavaScript implementation of binary search:

/**
 * 二分查找算法
 * @param {number[]} arr - 有序数组
 * @param {number} target - 目标元素
 * @return {number} - 目标元素的索引，未找到返回 -1
 */
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) {
      return mid; // 找到目标元素
    } else if (arr[mid] < target) {
      left = mid + 1; // 查找右半部分
    } else {
      right = mid - 1; // 查找左半部分
    }
  }

  return -1; // 未找到目标元素
}

// 示例
const arr = [1, 3, 5, 7, 9, 11, 13];
const target = 7;
const index = binarySearch(arr, target);
console.log(index); // 输出: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

3. Application Scenarios

1. Searching an ordered array: Quickly locate the position of an element in an ordered array.
2. Solving the problem: Used to solve certain algorithmic problems that require binary search, such as finding the peak element in an array.
3. data analysis: In data analysis, binary search is used to quickly find the location of a specific value.

---

4. Optimization and expansion

1. Recursive implementation: In addition to iterative implementation, binary search can also be implemented recursively.

/**
 * 递归实现二分查找算法
 * @param {number[]} arr - 有序数组
 * @param {number} target - 目标元素
 * @param {number} left - 左索引
 * @param {number} right - 右索引
 * @return {number} - 目标元素的索引，未找到返回 -1
 */
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1; // 未找到目标元素
  }

  const mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) {
    return mid; // 找到目标元素
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right); // 查找右半部分
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1); // 查找左半部分
  }
}

// 示例
const indexRecursive = binarySearchRecursive(arr, target);
console.log(indexRecursive); // 输出: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2. Find the first or last occurrence: The algorithm can be extended to find the position of the first or last target element in a sorted array through binary search.

---

V. Conclusion

Binary search is an efficient search algorithm that can quickly locate the target element in an ordered array by continuously halving the search range. Understanding and mastering the binary search algorithm is of great significance for solving many practical problems and optimizing program performance. I hope this article will help you understand and apply binary search.

---