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;

}