Binary Search

Medium30 minutes

Implement the classic Binary Search algorithm to find the index of a target value in a sorted array.

📋 Problem Requirements:

  1. Given a sorted array of integers and a target value
  2. Return the index of the target if found
  3. Return -1 if the target is not in the array
  4. Your solution must have O(log n) time complexity

💡 Example:

For array [1, 3, 5, 7, 9, 11] and target 7:

  • Check middle element (index 2): 5 < 7, search right half
  • Check middle of right half (index 4): 9 > 7, search left
  • Check index 3: 7 == 7, found! Return 3

🎯 Your Task:

Implement the binary_search function that takes a sorted array and a target value, and returns the index of the target or -1 if not found.

Examples:

Input: [[1, 3, 5, 7, 9, 11], 7]
Output: 3

Target 7 is at index 3

Input: [[1, 2, 3, 4, 5], 1]
Output: 0

Target 1 is at the beginning (index 0)

Input: [[1, 2, 3, 4, 5], 6]
Output: -1

Target 6 is not in the array

Constraints:

  • •0 ≤ len(arr) ≤ 10,000
  • •-10,000 ≤ arr[i] ≤ 10,000
  • •Array is sorted in ascending order
  • •All elements in the array are unique
  • •Solution must be O(log n) time complexity

Custom Test Input

Output

Loading Python environment...