/Binary-Search

Binary Search

TC - O(log(n))

Type 1

Binary Search in an array :

  • Find an element
  • Find the float or ceil of the element

Note: Here the array may consists of numbers or alphabets.

Type 2

Binary search in a matrix:

  • Matrix is sorted row wise
  • Matrix is sorted row and col wise

Type 3

Rotated sorted array:

  • Find pivot or min point in rotated sorted array or number of times array was rotated ( With or Without Duplicates)
  • Search for an element in rotated sorted array

Type 4

Sorted array with duplicates

  • Find 1st and last occurance of any element in a sorted array

Type 5

Infinite length sorted array

  • Search in Infinite sorted array
  • Find the Index of 1st one in an infinite length binary array

Type 6

Bitonic array

  • Max element in bitonic array
  • Search in bitonic array

Type 7

Misc

  • Square root of X using Binary search
  • Peak Element