Core Concept

Types of problems

  • Regular ones

  • Peak Element

  • Floor/Ceiling or Lower Bound/Upper Bound

  • What is the lowest occurrence / highest occurrence

  • Searching in a sorted 2D array

Important definitions

Floor/Lower Bound

Largest number which is smaller or equal to the given number.

This can also be called as immediate smallest number for a given number in array

Ceiling/Upper Bound Smallest number which is greater or equal to the given number

This can also be called as immediate largest number for a given number in array

Code for ascending binary search

class Solution {
    public int search(int[] nums, int target) {
        // Time complexity: O(log n), n -> length of input array
        // log n because search space is halved at each iteration
        // Space complexity: O(1), auxiliary space
        int low = 0, high = nums.length - 1;

        // Initiate iteration
        while(low <= high) {
            int mid = low + (high-low)/2; // Get the mid index
            
            // In this case, the nums[mid] == target, so we found the index                  
            if(nums[mid] == target) {
                return mid;
            }
            // If num[mid] is less than the target, we are looking out for a number greater than nums[mid]
            // Since the array is sorted in ascending order, search towards the right 
            else if(nums[mid] < target) {
                low = mid + 1;
            } 
            // If target is less than nums[mid], we are looking out for number lesser than nums[mid]
            // Subce array is sorted in ascending, search towards left
            else if(target > nums[mid]) {
                high = mid - 1;
            }
        }
        // If code flow has come here, it means the target is not present in the array
        return -1; 
    }
}

Why use `start<=end` and not `start < end`?

LogoBinary Search using start < end vs. using start <= endStack Overflow

If you replace start <= end it by start < end, there will be cases where your algorithm will not give a good answer.

Let's think about two cases.

  • You would like to search for 1 in the list [1]. In that case, start = 0, end = 0 the algorithm would return -1 if you change the loop condition to start < end.

  • You would like to search for 2 in the list [1, 2]. In that case, start = 0, end = 1. The algorithm will be set mid=(0+1)/2=0 in C. Thus arr[mid] < key. It will make start = 1, end = 1. Again, if you stop the loop here, the algorithm will return -1 instead of 1.

Calculating Mid

Original equationmid=start+end2\boldsymbol {{Original\ equation}} \\ \\ mid = \frac{start+end}2\\ \\
Better equationmid=start +(end−start)2\boldsymbol {{Better\ equation}} \\ \\ mid = start\ + \dfrac{(end-start)}2 \\ \\
mid=2∗start+end−start2In the above equation if we simplify, (2∗start−start)=startmid = \dfrac{2*start + end - start}2 \\ \\ In\ the\ above\ equation\ if\ we\ simplify,\ (2*start - start) = start \\ \\
Therefore, mid=start+end2Therefore,\ \boldsymbol {{mid = \dfrac{start + end}2}}

References:

PreviousDoubly Linked ListNextBookmarks

Last updated

Was this helpful?