PHP algorithm analysis: How to use binary search algorithm to quickly locate elements in an ordered array?

王林
Release: 2023-09-19 13:16:02
Original
846 people have browsed it

PHP algorithm analysis: How to use binary search algorithm to quickly locate elements in an ordered array?

PHP algorithm analysis: How to use the binary search algorithm to quickly locate elements in an ordered array?

Overview:
The binary search algorithm is an efficient search algorithm, which is suitable for finding specific elements in an ordered array. This article will introduce the principle of binary search algorithm in detail and give PHP code examples.

  1. Principle:
    The binary search algorithm quickly locates the target element by repeatedly reducing the search range by half. The process is as follows:
  2. First, narrow the search range to the beginning and end of the array;
  3. Then, calculate the index of the middle element and compare it with the target element;
  4. If the target element is equal to the middle element, return the search success directly;
  5. If the target element is smaller than the middle element, it means that the target element is to the left of the middle element, and the search range will be reduced to the left half;
  6. If the target element is larger than the middle element, it means that the target element is on the right side of the middle element, and the search range is reduced to the right half;
  7. Repeat the above steps until the target element is found, or the search range is empty, which means the search fail.
  8. Code example:
    The following is a code example of binary search implemented in PHP:
function binarySearch($arr, $target) {
    $left = 0;                              // 查找范围的左边界
    $right = count($arr) - 1;               // 查找范围的右边界

    while ($left <= $right) {
        $mid = floor(($left + $right) / 2); // 计算中间元素的索引

        if ($arr[$mid] == $target) {
            return $mid;                    // 找到目标元素,返回索引
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;               // 目标元素在中间元素的右侧
        } else {
            $right = $mid - 1;              // 目标元素在中间元素的左侧
        }
    }

    return -1;                              // 查找失败,返回-1
}

// 示例用法
$sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
$targetElement = 11;
$result = binarySearch($sortedArray, $targetElement);

if ($result == -1) {
    echo "目标元素 $targetElement 不存在于数组中。";
} else {
    echo "目标元素 $targetElement 的索引是 $result。";
}
Copy after login

In the above example, we define a file named binarySearch function to implement binary search. The function accepts two parameters: ordered array $arr and target element $target. During the running of the function, two variables $left and $right are used to represent the left and right boundaries of the search range. By continuously adjusting the boundaries to narrow the search range, the target element or Make sure it doesn't exist.

Finally, we defined an example usage that demonstrates how to use the binary search algorithm to find specific elements in an ordered array and output the result.

Conclusion:
The binary search algorithm is an efficient search algorithm, suitable for scenarios where specific elements are found in ordered arrays. By continuously narrowing the search scope, binary search can quickly locate the target element. In actual development, we can combine binary search algorithms for code design according to needs to improve search efficiency.

[Word count: 451 words]

The above is the detailed content of PHP algorithm analysis: How to use binary search algorithm to quickly locate elements in an ordered array?. For more information, please follow other related articles on the PHP Chinese website!

source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!