二分查找算法代码实现模板

• 前言
• 一、标准二分查找
• 二、在存在重复元素的数组中查找
• • 1.查找元素第一次出现的位置
  • 2.查找元素最后一次出现的位置
• 总结

维基百科： 在计算机科学中，二分查找算法（英语：binary search algorithm），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

记录一下个人比较喜欢一种的二分查找算法写法。

以下为 C# 代码实现：

public int BinarySearch(int[] nums, int target)
{
    int lo = 0;
    int hi = nums.Length;
    while (lo < hi)
    {
    	// 防溢出处理，一般情况下三种写法均可
    	// int mid = lo + (hi - lo) / 2;
    	// int mid = (lo + hi) >>> 1;
        int mid = lo + ((hi - lo) >> 1);
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] < target)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid;
        }
    }

    return -1;
}

以下为 C#代码实现：

public int SearchLeftMost(int[] nums, int target)
{
    int lo = 0;
    int hi = nums.Length;
    // 循环退出时 lo == hi
    while (lo < hi)
    {
        int mid = lo + ((hi - lo) >> 1);
        if (nums[mid] < target)
        {
            lo = mid + 1;
        }
        else 
        {
            hi = mid;
        }
    }
    // 如果没找到返回-1
    if (lo == nums.Length || nums[lo] != target)
    {
    	return -1;
    }
    return lo;
}

以下为 C# 代码实现：

public int SearchRightMost(int[] nums, int target)
{
    int lo = 0;
    int hi = nums.Length;
    // 循环退出时 lo == hi
    while (lo < hi)
    {
        int mid = lo + ((hi - lo) >> 1);
        if (nums[mid] > target)
        {
            hi = mid;
        }
        else
        {
            lo = mid + 1;    
        }
    }
    // 如果没找到返回-1
    if (lo == 0 || nums[hi - 1] != target)
    {
    	return -1;
    }
    
    return hi - 1;
}

二分查找思想简单，但是细节很多，不同的边界处理方式写法也会有所不同，以上是我个人最常用的一种写法。