Binary Search Review

Binary Search Code Review and Fixes

1
2
3
4
5
6
7
8
9
10
while (left < right) {  // ❌ Incorrect loop condition
    int mid = (left + right) / 2;
    if (array[mid] == target) {
        return mid;
    } else if (target > array[mid]) {
        left = mid;  // ❌ Wrong update (should be mid + 1)
    } else {
        right = mid; // ❌ Wrong update (should be mid - 1)
    }
}

1. Errors in Your Code

1️⃣ Incorrect Loop Condition

  • while (left < right) should be while (left <= right)
  • If you use <, you might miss checking the last element when left == right.

2️⃣ Wrong left and right Updates

  • left = mid; should be left = mid + 1;
  • right = mid; should be right = mid - 1;
  • Otherwise, the loop might get stuck in an infinite loop when left == mid or right == mid.

2. Fixed Code ✅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int binarySearch(int[] array, int target) {
        if (array == null || array.length == 0) return -1;
        int left = 0;
        int right = array.length - 1;

        while (left <= right) { // Fix condition
            int mid = left + (right - left) / 2; // Avoid integer overflow

            if (array[mid] == target) {
                return mid;
            } else if (target > array[mid]) {
                left = mid + 1; // Move right
            } else {
                right = mid - 1; // Move left
            }
        }
        
        return -1; // Target not found
    }
}
[视频内嵌代码贴在这]