Skip to content

Binary Search Basics

Table of Contents

34. Find First and Last Position of Element in Sorted Array

"""
-   Find the starting and ending position of a given target value in a sorted array.
"""

from bisect import bisect_left
from typing import List


# Binary Search
def searchRangeBS(nums: List[int], target: int) -> List[int]:
    def bisect_left(nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    left = bisect_left(nums, target)
    right = bisect_left(nums, target + 1) - 1

    if left <= right:
        return [left, right]

    return [-1, -1]


# Bisect
def searchRangeBSBisect(nums: List[int], target: int) -> List[int]:
    if not nums:
        return [-1, -1]

    left = bisect_left(nums, target)
    right = bisect_left(nums, target + 1) - 1

    return [left, right] if left <= right else [-1, -1]


nums = [5, 7, 7, 8, 8, 10]
target = 8
print(searchRangeBS(nums, target))  # [3, 4]
print(searchRangeBSBisect(nums, target))  # [3, 4]

#include <vector>
#include <iostream>
using namespace std;

class Solution
{
  int bisect_left(vector<int> &nums, int target)
  {
    int left = 0, right = (int)nums.size() - 1;

    while (left <= right)
    {
      int mid = left + (right - left) / 2;
      if (nums[mid] < target)
      {
        left = mid + 1;
      }
      else
      {
        right = mid - 1;
      }
    }
    return left;
  }

public:
  vector<int> searchRange(vector<int> &nums, int target)
  {
    int left = bisect_left(nums, target);
    if (left == (int)nums.size() || nums[left] != target)
    {
      return {-1, -1};
    }
    int right = bisect_left(nums, target + 1) - 1;
    return {left, right};
  }
};

int main()
{
  vector<int> nums = {5, 7, 7, 8, 8, 10};
  int target = 8;
  Solution s;
  vector<int> res = s.searchRange(nums, target);
  cout << res[0] << ", " << res[1] << endl;
  return 0;
}

35. Search Insert Position

"""
-   Return the index of the target if it is found. If not, return the index where it would be if it were inserted in order.
"""

from typing import List


# Binary Search
def searchInsert(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            return mid

    return left


nums = [1, 3, 5, 6]
target = 5
print(searchInsert(nums, target))  # 2

#include <cassert>
#include <vector>
using namespace std;

class Solution {
   public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 3, 5, 6};
    assert(solution.searchInsert(nums, 5) == 2);
    assert(solution.searchInsert(nums, 2) == 1);
    assert(solution.searchInsert(nums, 7) == 4);
    assert(solution.searchInsert(nums, 0) == 0);
    return 0;
}

"""
- Implement binary search algorithm.
"""

from typing import List


# Binary Search [left, right]
def search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            return mid

    return -1


# Binary Search [left, right)
def search_half_open(nums: List[int], target: int) -> int:
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid
        else:
            return mid

    return -1


# Binary Search (left, right)
def search_open_interval(nums: List[int], target: int) -> int:
    left, right = -1, len(nums)

    while left + 1 < right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid
        elif nums[mid] > target:
            right = mid
        else:
            return mid

    return -1


if __name__ == "__main__":
    nums = [-1, 0, 3, 5, 9, 12]
    target = 9
    assert search(nums, target) == 4
    assert search_half_open(nums, target) == 4
    assert search_open_interval(nums, target) == 4

744. Find Smallest Letter Greater Than Target

from typing import List


# Binary Search
def nextGreatestLetter(letters: List[str], target: str) -> str:
    left, right = 0, len(letters)

    while left < right:
        mid = left + (right - left) // 2
        if letters[mid] > target:
            right = mid
        else:
            left = mid + 1

    return letters[left] if left < len(letters) else letters[0]


letters = ["c", "f", "j"]
target = "a"
print(nextGreatestLetter(letters, target))  # c

2529. Maximum Count of Positive Integer and Negative Integer

from bisect import bisect_left, bisect_right
from typing import List


# Binary Search
def maximumCount(nums: List[int]) -> int:
    pos = bisect_left(nums, 0)
    neg = len(nums) - bisect_right(nums, 0)

    return max(pos, neg)


nums = [-2, -1, -1, 1, 2, 3]
print(maximumCount(nums))  # 3

Comments