LeetCode 704. Binary Search

Problem Link: 704. Binary Search

Binary Search (Left-Closed Right-Closed) Implementation

class Solution {
public:
   int search(vector<int>& numbers, int value) {
       int left = 0, right = numbers.size() - 1;
       while (left <= right) {
           int middle = (left + right) / 2;
           if (numbers[middle] > value) {
               right = middle - 1;
           } else if (numbers[middle] < value) {
               left = middle + 1;
           } else {
               return middle;
           }
       }
       return -1;
   }
};

This approach uses a left-closed and right-closed interval. The loop condition ensures that the search space is always valid. Simialrly, we can implement other variations of binary search.

Binary Search (Left-Closed Right-Open) Implementation

class Solution {
public:
   int search(vector<int>& numbers, int value) {
       int left = 0, right = numbers.size();
       while (left < right) {
           int middle = (left + right) / 2;
           if (numbers[middle] > value) {
               right = middle;
           } else if (numbers[middle] < value) {
               left = middle + 1;
           } else {
               return middle;
           }
       }
       return -1;
   }
};

LeetCode 27. Remove Element

Problem Link: 27. Remove Element

class Solution {
public:
   int removeElement(vector<int>& array, int value) {
       vector<int>::iterator it;
       for (it = array.begin(); it != array.end();) {
           if (*it == value) {
               it = array.erase(it);
           } else {
               it++;
           }
       }
       return array.size();
   }
};

Details: The loop uses conditional logic to manage the iterator correctly. For example, when removing elements with a specific value from a list like {1, 2, 3, 3, 3, 4, 5}, using a simple for loop without conditions may skip some elements. The erase method returns the next valid iterator, so proper hadnling is required to avoid missing any elements.