二分查找

介绍

二分查找（Binary Search）是一种高效的查找算法，主要用于在有序数组中查找指定的元素。二分查找的基本思想是通过不断缩小查找范围，将查找时间复杂度从线性的O(n)降低到对数的O(log n)。

具体实现时，从有序数组的中间元素开始比较，如果该中间元素等于目标元素，则返回该元素的索引；如果该中间元素大于目标元素，则在数组的左半部分继续查找；如果该中间元素小于目标元素，则在数组的右半部分继续查找。重复这个过程，直到找到目标元素或者查找范围为空为止。

二分查找的时间复杂度为O(log n)，其中n为有序数组的大小。由于二分查找需要有序数组作为基础，因此其适用范围相对较小，但在查找频繁、数组大小较大或者需要多次查找的情况下，二分查找具有明显的优势。

需要注意的是，在实现二分查找时，需要确保有序数组的正确性，同时也需要注意边界条件的处理，例如数组为空或者只包含一个元素的情况。

代码

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid;
            }

            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
        int result = binarySearch(arr, target);

        if (result == -1) {
            System.out.println("Element not found in the array.");
        } else {
            System.out.println("Element found at index " + result);
        }
    }
}

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid;
        }

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

const arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
const target = 23;
const result = binarySearch(arr, target);

if (result === -1) {
    console.log("Element not found in the array.");
} else {
    console.log("Element found at index " + result);
}

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binary_search(arr, target)

if result == -1:
    print("Element not found in the array.")
else:
    print("Element found at index", result)

package main

import "fmt"

func binarySearch(arr []int, target int) int {
	left := 0
	right := len(arr) - 1

	for left <= right {
		mid := (left + right) / 2

		if arr[mid] == target {
			return mid
		}

		if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return -1
}

func main() {
	arr := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
	target := 23
	result := binarySearch(arr, target)

	if result == -1 {
		fmt.Println("Element not found in the array.")
	} else {
		fmt.Println("Element found at index", result)
	}
}

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 23;
    int result = binarySearch(arr, size, target);

    if (result == -1) {
        printf("Element not found in the array.\n");
    } else {
        printf("Element found at index: %d\n", result);
    }

    return 0;
}

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int main() {
    std::vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target = 23;
    int result = binarySearch(arr, target);

    if (result == -1) {
        std::cout << "Element not found in the array." << std::endl;
    } else {
        std::cout << "Element found at index: " << result << std::endl;
    }

    return 0;
}

<?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;
        }

        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return -1;
}

$arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$target = 23;
$result = binarySearch($arr, $target);

if ($result == -1) {
    echo "Element not found in the array.";
} else {
    echo "Element found at index: " . $result;
}

?>