二分搜索
2022-04-25 23:02:01

二分搜索
数组必须是排序好的
java 实现

public class App {
    public static void main(String[] args) throws Exception {
        // 目标数组
        int[] arr1 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        // 目标元素
        int dstNum = 10;
        // 左索引
        int leftIndex = 0;
        // 右索引
        int rightIndex = arr1.length - 1;
        // 中间索引
        int midIndex = (leftIndex + rightIndex) / 2;

        // 目标位置
        int dstIndex = -1;
        while (leftIndex <= rightIndex) {
            // 如果命中
            if (arr1[midIndex] == dstNum) {
                dstIndex = midIndex;
                break;
            }

            if (arr1[midIndex] > dstNum) {
                // 如果中间数大于目标数，右索引左移到中间位置-1
                rightIndex = midIndex - 1;
            } else {
                // 中间数大于目标数， 左索引右移到中间位置 +1
                leftIndex = midIndex + 1;
            }

            // 重新计算midIndex
            midIndex = (leftIndex + rightIndex) / 2;

        }
        System.out.println("结果:" + dstIndex);

    }
}

python 实现

# coding: utf-8
if __name__ == '__main__':
    arr = [1,2,3,4,5,6,7,8,9]
    left_index = 0
    right_index = len(arr)-1
    dst_num = 6
    dst_index = -1
    mid_index = int((left_index + right_index) / 2)
    while left_index <= right_index:
        if arr[mid_index] == dst_num:
            dst_index = mid_index
            break

        if arr[mid_index] < dst_num:
            left_index = mid_index + 1
        else:
            right_index = mid_index - 1
        
        mid_index = int((left_index + right_index) / 2)
    
    print(f"结果:{mid_index}")

优化
防止整数相加溢出
计算中位数使用

int midIndex = leftIndex + ((rightIndex - leftIndex) >> 1)

python

mid_index = left_index + ((right_index - left_index) >> 1)