INFO Binary Search called “Recherche Dichotomique” in French is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. APPROACH Find the Exact Value class Solution { public: int search(vector<int> &nums, int target) { int leftPtr = 0; int rightPtr = nums.size() - 1; while (leftPtr <= rightPtr) { int m = (leftPtr + rightPtr) / 2; if (nums[m] == target) return m; else if (nums[m] < target) leftPtr = m + 1; else rightPtr = m - 1; } return -1; } }; Find Upper bound class Solution { public: int search(vector<int> &nums, int target) { int leftPtr = 0; int rightPtr = nums.

PROBLEM You are given an m x n integer matrix matrix with the following two properties: Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise. You must write a solution in O(log(m * n)) time complexity. Example1 *Input*: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 *Output*: true Example2 *Input*: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 *Output*: false SOLVING we’ll use Binary Search exact value to solve this problem

PROBLEM In an sorted array [1, 3, 5, 6, 8], you want to know the index to insert your target, 5 In an sorted array [1, 3, 5, 6, 8], you want to know the index to insert your target, 2 SOLVING Use of Binary Search method. This code will return the index 2, where the target already is This code will return the index 1 where the target should be Steps Place Left Pointer at 0 and Right Pointer to the last element Until Left Element is inferior to Right Element: Get the element between left and right Middle Index=(Left Index - RIght Index) / 2 If Middle Element equal the target, return If it’s inferior, Left Pointer becomes the Middle Pointer Otherwise it’s superior, and so Right Pointer become the Middle Pointer If the loop is finished return the Left Pointer Code #include <iostream> #include <vector> int searchInsert(std::vector<int> &nums, int target) { int l = 0; int r = nums.