binary Search

[Khandagale-Saurabh]

Mid ki calculate : int mid= start+(end-start)/2; int can store max avlue 10^9 when start and end will be at its peek value it will give us wrong value;

for higher index it will lead to problem of giving wrong value so we use mid in this way

Complexcity : logn==> Array length is 8 then logn=> 3 log2(8)=>3

==============================

why to use

lets assume integer range is 0-5 but my array size is 10 then now i want to acess 8th index /elemnt so in binary search it will nerver go bevond the 0-5 index range so to avoid we use

s=0,e=10

[Khandagale-Saurabh]

// Q1] First & Last Occurance  of element

class Solution {
    public int[] searchRange(int[] nums, int target) 
    {

        int ans[]={-1,-1};

        for(int i=0;i<=nums.length-1;i++)
        {

             if(nums[i]==target && ans[0]==-1)
             {
                 ans[0]=i;
             }
             if(nums[nums.length-1-i]==target && ans[1]==-1)
             {
                 ans[1]=nums.length-1-i;
             }
        }
       return ans;  
    }
}

By binary Search we can also do this in 2 step
1] make 2 function one for first and second for last
and manage  if(arr[mid]==data)=> res=mid => end=mid-1; //first occurance

2]  manage  if(arr[mid]==data)=> res=mid => start=mid+1; //Last occurance

Q2] Count in sorted array
find difference in last and first occurance.

Q3] Serch in Sorted Roted Aray

=> Try to find sorted part of array and thensearch in sorted part
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Case 1: find target
            if (nums[mid] == target) {
                return mid;
            }

            // Case 2: subarray on mid's left is sorted
            else if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            // Case 3: subarray on mid's right is sorted
            else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

Time complexity: O(log⁡n)
Space complexity: O(1)

Q4] Search in nearly sorted array

<script>
// in an almost sorted array

// A recursive binary search based function.
    // It returns index of x in given array
    // arr[l..r] is present, otherwise -1
function binarySearch(arr,l,r,x)
{
    if (r >= l)
        {
            let mid = l + Math.floor((r - l) / 2);

            // If the element is present at
            // one of the middle 3 positions
            if (arr[mid] == x)
                return mid;
            if (mid > l && arr[mid - 1] == x)
                return (mid - 1);
            if (mid < r && arr[mid + 1] == x)
                return (mid + 1);

            // If element is smaller than mid, then
            // it can only be present in left subarray
            if (arr[mid] > x)
                return binarySearch(arr, l, mid - 2, x);

            // Else the element can only be present
            // in right subarray
            return binarySearch(arr, mid + 2, r, x);
        }

        // We reach here when element is
        // not present in array
        return -1;
}

// Driver code
let arr=[3, 2, 10, 4, 40];
let n = arr.length;
let x = 4;
let result = binarySearch(arr, 0, n - 1, x);
if(result == -1)
    document.write("Element is not present in array<br>");
else
    document.write("Element is present at index " +
                result+"<br>");

// This code is contributed by unknown2108
</script>

you can also do with priority queue create PQ with  k+1 size and add it only k elemnts

[Khandagale-Saurabh]

Q6] Floor & Ciel in Sorted Array
int lo=0,hi=arr.length-1;
int floor=ciel=0;

while(lo<hi)
{
int mid=hi+lo/2;
 if(data>arr[mid])
{
lo=mid+1;
floor=arr[mid] ; //or mid for index
}
else if(data<arr[mid])
{
hi=mid-1;
cile=arr[mid]
}
else
{
ciel=foor=arr[mid];
break;
}

}

[Khandagale-Saurabh]

Q13] Find position of an element in an Infinite Sorted Array.

problem is that we dont know the end index in this case so , we have to just incremnet end index by 2

initally start =0,end=1;

int low =0,high=1;
while(key>arr[hight])
{
low=high;
high=high*2;
}

binarySearch(arr,low,high,target);

[Khandagale-Saurabh]

Q] First And Last Index