DEV Community: Sudeep .U

Binary Search - Check rotated sorted array

Sudeep .U — Sat, 28 Jun 2025 18:20:27 +0000

Key points :
1) Find count of pivot elements
2) Edge case - check last element > first element
To check this - num[i] > num[(i+1)%nums.length]

class Solution {
    public boolean check(int[] nums) {
    int c = 0;
    for(int i = 0;i < nums.length; i++){
        if(nums[i] > nums[(i+1)%nums.length]){
            c++;
        }
        if(c > 1){
            return false;
        }
    }
    return true;

    }
}

Binary Search -Matrix Search

Sudeep .U — Thu, 26 Jun 2025 17:43:59 +0000

Key points -
1) Search space - 0 to row*cols-1;
Reason - when directly divided by no of columns in a row
You get directly the row and col
Eg : 11 is mid and cols in a row is 4
11/4 -> 2nd row and 3 col in matrix
which is 12th ele -> 3rd row 4th ele
2) Once row and col is derived from mid
Same binary search logic is applied

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int low = 0;
        int high = rows * cols - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int row = mid / cols;
            int col = mid % cols;

            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return false;
    }
}

Binary Search

Sudeep .U — Thu, 26 Jun 2025 17:40:08 +0000

Key points

Calculate mid - int mid = low + (high - low) / 2;
if mid is lesser than target increase low by 1 or else mid is greater than target then high decrease by 1
the loop condition - low < = high
take ex : 1,3,5,7,9 target =9
we have to track at point low == high so if its equal to target.

class Solution {
    public int search(int[] nums, int target) {
        int low=0;
        int high = nums.length-1;
        while(low<high){
            int mid = (low+high)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid]<target){
                low=mid+1;
            }
            else{
                high=mid-1;
            }
        }
        return -1;
    }
}

DSA

Sudeep .U — Sat, 01 Feb 2025 19:11:41 +0000

I am an amateur trying to debug and learn DSA.
Lets analyse the problem and break it down so we find the pattern as a solution.
Lets go !!!!

Note : Following multiple sde sheets will share where the approach was taken from.

Thank you