二分法题目：在有序数组中A内，查找数组中的某一个元素的下标（本题是从由小到大的顺序）

二分查找算法，也称为折半查找算法，是一种在有序数组中查找特定元素的高效算法。它的基本思想是将查找的区间逐渐缩小，直到找到目标元素或者确定目标元素不存在。

算法步骤如下：

1. 初始化：首先，确定数组的左右边界，通常初始时左边界为数组的起始索引，右边界为数组的末尾索引。

2. 找到中间元素：计算左右边界的中间索引，然后取得该索引处的元素值。

3. 比较中间元素：

   • 如果中间元素等于目标值，查找成功，返回元素索引。
   • 如果中间元素大于目标值，说明目标值应该在左半边，将右边界移动到中间索引的左边一位。
   • 如果中间元素小于目标值，说明目标值应该在右半边，将左边界移动到中间索引的右边一位。

4. 重复：在新的查找区间中，重复步骤2和步骤3，直到左边界大于右边界，此时查找失败，返回-1，或者返回指示元素不存在的其他值。

算法特点：

• 二分查找算法的时间复杂度是O(log n)，其中n是数组的大小。这是因为每一次比较都将查找范围缩小为原来的一半。

• 但是，二分查找算法要求输入的数据必须是有序的。如果数组无序，需要事先进行排序操作。

• 由于二分查找每次将查找范围缩小为一半，因此它的效率非常高，尤其是在大型数据集中的查找操作。

• 二分查找算法是一种迭代的算法，也可以使用递归实现。

Java版：

package LeetCode_1.Binary_search;
//小淼的算法之路
 
//二分法题目：在有序数组中A内，查找数组中的某一个元素的下标（本题是从由小到大的顺序）
 
 
public class Binary_search {
    //二分查找算法版本1.0
    public static int BinarySearchBasic(int[] a, int target){
        int i = 0,j = a.length -1;//设置指针和初值
        while (i <= j){
            int m = (i + j)>>>1;//m：中间值
            if(target < a[m]){//若查找的在中间值左边（小于中间值），最大值指针j占据中间值-1的位置，在进行计算
                j = m -1;
            } else if (a[m] < target){//若查找的在中间值右边（大于中间值），最小值指针j占据中间值+1的位置，在进行计算
                i = m + 1;
            } else {
                return m;//否则就是target值与中间值相等，直接返回中间值
            }
        }
        return -1;//不存在时返回-1，因为能找到的都在数组当中，在数组中的都有一个索引值，所以能找到的输出的数组索引值不可能为-1
    }
    /*本题问题1：为什么i<=j 意味着区间未比较的元素，而不是i
     *       答：因为i,j 它们指向的元素也会参与比较，若i
     * 本题问题2：为什么int m = (i + j)>>>1;，而不是int m = (i + j) / 2;  ?
     *       答：如果使用int m = (i + j) / 2 来确定中间值的话多次循环会有问题：这与二进制的第一位是不是符号位有关（1：负，0：正）。
     *           然而int m = (i + j)>>>1 这种方式：将i+j表示成的二进制整体向右移动一位（二进制对应的十进制做/2操作）
     * */
 
    //二分查找算法版本2.0
    public static int BinarySearchUpgrades(int[] a, int target){
        int i = 0,j = a.length;         //第一处改动
        while (i < j){                  //第二处改动
            int m = (i + j)>>>1;
            if(target < a[m]){
                j = m;                  //第三处改动
            } else if (a[m] < target){
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }
 
    //测试类
    public static void main(String[] args) {
        int[] a = {7,13,21,30,38,44,52,53,78,79,88,89,91,92,93,94};
        int target = 92;
        long startTime = System.nanoTime();;//开始时时间点
        int result = BinarySearchBasic(a, target);//执行的算法
        long endTime = System.nanoTime();//结束时时间点
        long elapsedTime = endTime - startTime;//算法占用时间
        if (result != -1) {
            System.out.println("二分查找法1.0版本----------"+"目标值 " + target + " 在数组中的索引是 " + result+"\n"+"算法执行时间（纳秒）: " + elapsedTime);
        } else {
            System.out.println("二分查找法1.0版本----------"+"目标值 " + target + " 未在数组中找到");
        }
        long startTime_1 = System.nanoTime();;//开始时时间点
        int result_1 = BinarySearchUpgrades(a, target);
        long endTime_1 = System.nanoTime();//结束时时间点
        long elapsedTime_1 = endTime_1 - startTime_1;//算法占用时间
        if (result_1 != -1) {
            System.out.println("二分查找法2.0版本----------"+"目标值 " + target + " 在数组中的索引是 " + result_1+"\n"+"算法执行时间（纳秒）: " + elapsedTime_1);
        } else {
            System.out.println("二分查找法2.0版本----------"+"目标值 " + target + " 未在数组中找到");
        }
    }
}
 
 

JavaScript：

function binarySearchBasic(a, target) {
    let i = 0, j = a.length - 1; // 设置指针和初值
    while (i <= j) {
        let m = (i + j) >>> 1; // m：中间值
        if (target < a[m]) {
            // 若查找的在中间值左边（小于中间值），最大值指针j占据中间值-1的位置，在进行计算
            j = m - 1;
        } else if (a[m] < target) {
            // 若查找的在中间值右边（大于中间值），最小值指针j占据中间值+1的位置，在进行计算
            i = m + 1;
        } else {
            return m; // 否则就是target值与中间值相等，直接返回中间值
        }
    }
    return -1; // 不存在时返回-1，因为能找到的都在数组当中，在数组中的都有一个索引值，所以能找到的输出的数组索引值不可能为-1
}
 
function binarySearchUpgrades(a, target) {
    let i = 0, j = a.length; // 第一处改动
    while (i < j) { // 第二处改动
        let m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m; // 第三处改动
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}
 
const a = [7, 13, 21, 30, 38, 44, 52, 53, 78, 79, 88, 89, 91, 92, 93, 94];
const target = 92;
 
let startTime = performance.now(); // 开始时时间点
let result = binarySearchBasic(a, target);
let endTime = performance.now(); // 结束时时间点
let elapsedTime = endTime - startTime; // 算法占用时间
 
if (result !== -1) {
    console.log(`二分查找法1.0版本---------- 目标值 ${target} 在数组中的索引是 ${result}\n算法执行时间（毫秒）: ${elapsedTime}`);
} else {
    console.log(`二分查找法1.0版本---------- 目标值 ${target} 未在数组中找到`);
}
 
let startTime1 = performance.now(); // 开始时时间点
let result1 = binarySearchUpgrades(a, target);
let endTime1 = performance.now(); // 结束时时间点
let elapsedTime1 = endTime1 - startTime1; // 算法占用时间
 
if (result1 !== -1) {
    console.log(`二分查找法2.0版本---------- 目标值 ${target} 在数组中的索引是 ${result1}\n算法执行时间（毫秒）: ${elapsedTime1}`);
} else {
    console.log(`二分查找法2.0版本---------- 目标值 ${target} 未在数组中找到`);
}