Посчитать среднее число шагов при двоичном поиске для массива

@Kadet12 · Регистрация: 29.01.2019

Студворк — интернет-сервис помощи студентам

Задания по теме Сортировка. Двоичный поиск. Матрицы. HELP Python Чайник)
Напишите программу, которая считает среднее число шагов при двоичном поиске для массива из 32 элементов в диапазоне 0..100. Для поиска используйте 1000 случайных чисел в этом же диапазоне.

@Catstail · 02.02.2019, 12:08

Python

def binSearch(arr,target):
    a=0
    b=len(arr)-1
    if target < arr[a] | target > arr[b]:
        return (-1,0)
    if target == arr[a]:
        return (0,1)
    if target == arr[b]:
        return (b,1)
    counter=0
    while(True):
        if (b-a)<=1:
            return (-1,counter)
        counter+=1
        c=(a+b)//2
        if target==arr[c]:
            return (c,counter)
        if arr[c]>target:
            b=c
        else:
            a=c
            
arr=[] 
for i in range(33):
    arr+=[int(100*random.random())]
arr=sorted(arr)
            
a=int(100*random.random())
print(str(arr))
print(a)
res=binSearch(arr,a)
print(res)

https://ideone.com/gpnl0a

@Kadet12 -5 / 2 / 0 Регистрация: 29.01.2019 Сообщений: 278
		1
	Посчитать среднее число шагов при двоичном поиске для массива 01.02.2019, 17:30. Показов 7402. Ответов 1 Метки python 3.7, python shell (Все метки) Задания по теме Сортировка. Двоичный поиск. Матрицы. HELP Python Чайник) Напишите программу, которая считает среднее число шагов при двоичном поиске для массива из 32 элементов в диапазоне 0..100. Для поиска используйте 1000 случайных чисел в этом же диапазоне. 0

Опции темы

Посчитать среднее число шагов при двоичном поиске для массива

Решение