Given a sorted array and a target, return the target's index, or -1 if absent. O(log N).
Binary search halves the search space each iteration by comparing the middle element to the target. Simple in principle, notoriously easy to get wrong — off-by-one errors, integer overflow on (lo + hi) / 2, infinite loops when the halving misses a case.
Read the array on line 1 (space-separated), the target on line 2. Output the index (0-based), or -1.
The classic gotcha: mid = (lo + hi) / 2 overflows for large arrays. Prefer lo + (hi - lo) / 2. Small in Java/C where int is 32-bit; irrelevant in Python (arbitrary precision).
-1 0 3 5 9 12 9
4
-1 0 3 5 9 12 2
-1
Runnable starter code. Click "Try in playground" to open pre-loaded with the test fixtures.
nums = list(map(int, input().split()))
target = int(input())
lo, hi = 0, len(nums) - 1
ans = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: ans = mid; break
elif nums[mid] < target: lo = mid + 1
else: hi = mid - 1
print(ans)
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] parts = sc.nextLine().split(" ");
int[] nums = new int[parts.length];
for (int i = 0; i < parts.length; i++) nums[i] = Integer.parseInt(parts[i]);
int target = Integer.parseInt(sc.nextLine().trim());
int lo = 0, hi = nums.length - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) { ans = mid; break; }
else if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
System.out.println(ans);
}
}
#include <bits/stdc++.h>
using namespace std;
int main() {
string line; getline(cin, line);
vector<int> nums; stringstream ss(line); int x; while (ss >> x) nums.push_back(x);
int target; cin >> target;
int lo = 0, hi = (int)nums.size() - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) { ans = mid; break; }
else if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
cout << ans << "\n";
}