Implement iterative binary search

Summary

Write an iterative binary search to locate a target value in a sorted list. Return the index if found, otherwise -1.

Problem statement

Given a sorted list of integers (ascending) and a target integer, implement an iterative binary search function binary_search(arr, target). The function should return the index of the target if it exists in the list. If the target is not present, return -1. The search should be performed iteratively (no recursion). If the list contains duplicate values equal to the target, returning any valid index of target is acceptable.

Task

Implement an iterative binary search that returns the index of the target or -1 if not present.

Examples

Input format

A sorted list of integers 'arr' and an integer 'target' passed to binary_search(arr, target).

Output format

An integer index where target is found, or -1 if not found.

Constraints

0 <= len(arr) <= 10^5. Values fit in standard Python int. Time complexity should be O(log n). Use iterative approach.

Samples