Explore - LeetCode

What is Binary Search?

Binary Search is one of the most fundamental and useful algorithms in Computer Science. It describes the process of searching for a specific value in an ordered collection.

Terminology used in Binary Search: Target - the value that you are searching for Index - the current location that you are searching Left, Right - the indicies from which we use to maintain our search Space Mid - the index that we use to apply a condition to determine if we should search left or right

Base Case

public int classicBinarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Find Minimum in Rotated Sorted Array Case

public int findMin(int[] nums) {
    if (nums.length == 0) return -1;
    int hi = nums.length - 1;
    int lo = 0;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
				//!important
        if (nums[mid] < nums[hi]) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return nums[lo];
}

Find Max In Bitonic Array

public int findMax(int[] arr) {
  int lo = 0, hi = arr.length - 1;
  while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
			//!important
      if (arr[mid] <= arr[mid + 1]) {
          lo = mid + 1;
      } else {
          hi = mid;
      }
  }
  return arr[lo];
}

For some problem we might do binary search twice, or apply certain conditions according to sorting order.

Number Range

public int[] searchRange(int[] arr, int target) {
    int[] res = new int[2];
    res[0] = findInRange(arr, target, true);
    res[1] = findInRange(arr, target, false);
    return res;
}

private int findInRange(int[] arr, int target, boolean low) {
    int lo = 0, hi = arr.length - 1, keyIndex = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) {
            lo = mid + 1;
        } else if (arr[mid] > target) {
            hi = mid - 1;
        } else {
						//!important
            keyIndex = mid;
            if (low) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
    }
    return keyIndex;
}

Or we can apply post processing step.

Min Difference Element