Binary Search – Incorrect comparison causes potential missed target #32678
Description
LeetCode Username
pubbojushashank
Problem Number, Title, and Link
704 , Binary Search , https://leetcode.com/problems/binary-search
Bug Category
Missing test case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Bug Description
In my submission, I accidentally wrote:
else if (arr[mid] <= target) {
left = mid + 1;
}
Instead of:
else if (arr[mid] < target) {
left = mid + 1;
}
The condition <= target is logically incorrect because when arr[mid] == target the algorithm should already return the index.
Using <= unnecessarily shifts the left pointer forward, which can skip the correct index in certain cases
Language Used for Code
Java
Code used for Submit/Run operation
class Solution {
public int search(int[] arr, int target) {
int left =0 , right = arr.length-1;
while(left<=right){
int mid = (left+right)/2;
if(arr[mid]==target) return mid;
else if(arr[mid]<=target){
left = mid+1;
}
else{
right = mid-1;
}
}
return -1;
}
}Expected behavior
Binary search should only move left when arr[mid] < target, not when arr[mid] == target.
Screenshots
No response
Additional context
No response