Modified Binary Search

1). Simple Search in Sorted Array (Easy)

_Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1._

[(https://leetcode.com/problems/binary-search?envType=problem-list-v2&envId=binary-search)]

• This is the basic and easiest form of binary search algorithm which is used to search an particular element in an array, Binary search is an alternative of Linear Search to reduce the time complexity of searching algorithm, It is the most optimized searching algorithm till now in DSA.

Pattern: Try to search the element in 7 or less tries.

Note: Binary Search are not only bound to use with array, It can be implemented in Sorted array, array divided into two sorted array or in sorted input space.

Algorithm:

1). Set Zeroth index as Low & Last index as High.
Low = arr[0] & High = arr[n-1]

2).Find mid i.e middle index of High and Low.
mid = (low+high)/2
But
mid = low+(high-low)/2 is advised to use to avoid the integer overflow.

3). While low<=high -
Compare the arr[mid] element with target.

• if arr[mid]==target
  return mid

• else if (arr[mid]<target)
  low = mid+1

• else
  high = mid-1

4). If target is not in the array then low will become greater than high, thus loop will break
return -1

Code:

int search(int* nums, int numsSize, int target) {


    int low = 0;
    int high =numsSize-1;

    while(low<=high){
         int mid = (low+high)/2;

        if(nums[mid]==target){
            return mid;
        }
        else if(nums[mid]>target){
            high = mid-1;
        }
        else {
            low=mid+1;
        }

    }
    return -1;
}

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

---

2). Search Insert Position (Easy)

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order._

Example:
Input: arr = [1,3,5,6], target = 2
Output: 1
Explanation: target is not present in the array and it is best fitted at 1st Index so Output is 1.

[https://leetcode.com/problems/search-insert-position?envType=problem-list-v2&envId=binary-search]

• This Problem is an Modified version of binary search in which a little modification in the binary search algorithm is needed in order to solve this problem. This problem is asking to return the index of target element if present in the array else, If target is not present in array then return the position index where the target should be best fitted in the array.

Modification:

In order to return the index where the target element should be present if it was in the array then we have to return low in last when the loop breaks i.e whenlow<=highfails then the low will be the index where the target should be inserted in the array.

Why to return low? Why not high?

When the loop ends the condition becomes low = high+1 -
So now:

• All elements before low are less than target

• All elements after or equal to low are greater than target

💡 In other words:

• low is exactly the index where target should be inserted.

Algorithm:

1). Set Zeroth index as Low & Last index as High.
Low = arr[0] & High = arr[n-1]

2).Find mid i.e middle index of High and Low.
mid = (low+high)/2
But
mid = low+(high-low)/2 is advised to use to avoid the integer overflow.

3). While low<=high -
Compare the arr[mid] element with target.

• if arr[mid]==target
  return mid

• else if (arr[mid]<target)
  low = mid+1

• else
  high = mid-1

4). If target is not in the array then low will become greater than high, thus loop will break
return low

Code:

int searchInsert(int* nums, int numsSize, int target) {
    int low=0; int high=numsSize-1;

    while(low<=high){
        int mid = (low+high)/2;

        if(nums[mid]==target){
            return mid;
        }

        else if(nums[mid]>target){
            high = mid - 1;
        }

        else{
            low = mid + 1;
        }
    }

    return low;

}

---

1). First and last Position of element in sorted array (Medium)

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].

Example:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Explanation: target 8 is first found at index 3 and then at index 4. So, [3,4]

[https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array]

• This problem also requires some modification in binary search algorithm in order to solve this problem, In this question we just need to return the index of target element when it is occurred first time and then the last time.

Modification -

In this type of problem we just need to use binary search two times at once. The first binary search will return the index of target at which target is first occurred and second binary search will give return the index of second occurrence.

Algorithm:

0). Initialize an array of size 2 and set as arr=[-1,-1].

For First Occurrence....
1). Set Zeroth index as Low & Last index as High.
Low = arr[0] & High = arr[n-1]
2).Find mid i.e middle index of High and Low.
mid = (low+high)/2
But
mid = low+(high-low)/2 is advised to use to avoid the integer overflow.
3). While low<=high -
Compare the arr[mid] element with target.

• if arr[mid]==target { set arr[0]=mid; // assume the index as first occurrence and high = mid-1; // Check more in left side if target is present there }
• else if (arr[mid]<target) low = mid+1
• else high = mid-1

For Second Occurrence....
1). Set Zeroth index as Low & Last index as High.
Low = arr[0] & High = arr[n-1]
2).Find mid i.e middle index of High and Low.
mid = (low+high)/2
But
mid = low+(high-low)/2 is advised to use to avoid the integer overflow.
3). While low<=high -
Compare the arr[mid] element with target.

• if arr[mid]==target { set arr[1]=mid; // assume the index as second occurrence and low = mid+1; // Check more in right side if target is present there }
• else if (arr[mid]<target) low = mid+1
• else high = mid-1

4). If target is not in the array then low will become greater than high, thus loop will break
return arr

Code:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        vector<int> arr = {-1,-1};
        int n =nums.size();
        if(n==0)
        return arr;

        int low =0;
        int high = n-1;

        while(low<=high){
            int mid = (high+low)/2;

            if(nums[mid]==target){
            arr[0]=mid;
            high = mid-1;
        }

           else if(nums[mid]>target)
            high = mid-1;

            else
            low=mid+1;


        }

         low=0;
         high = n-1; 
         while(low<=high){
            int mid = (high+low)/2;

            if(nums[mid]==target){
            arr[1]=mid;
            low = mid+1;
            }


           else if(nums[mid]>target)
            high = mid-1;

            else
            low=mid+1;


        }
        return arr;
    }
};