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
Target present in middle
Input
binary_search([1, 2, 3, 4, 5], 3)
Output
2
Explanation
3 is at index 2 in the list.
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
Sample input 0
binary_search([1, 2, 3, 4], 4)
Sample output 0
3
Explanation 0
4 is at index 3.
AI assistant
Ask me anything!
Need help? I can explain the core idea behind this problem, review your current code, and give targeted hints. Use “Teach Theory” for the concept, “Get AI hint” for a quick scaffold nudge, or ask a specific question below.
Chat history is temporary and will not be saved.
Free preview includes 1 Teach Theory response and 1 AI hint on each of the first 3 lessons in this module.