Binary Search

Binary Search is a search algorithm used to find the position of a specific element in a sorted array or list. It’s a highly efficient algorithm that works by repeatedly dividing the search range in half.

Binary Search is highly efficient because with each comparison, it eliminates half of the remaining search space. As a result, its time complexity is O(log n), where n is the number of elements in the array. This is in contrast to linear search, which has a time complexity of O(n) and checks each element sequentially.

However, Binary Search has a limitation: it requires the array to be sorted. If the array isn’t sorted, you’ll need to sort it first or consider other search algorithms.

• Peak Index in a Mountain Array
  Given an array of integers arr that represents a mountain, you need to find the peak index. A peak index is an index such that arr[i – 1] < arr[i] > arr[i + 1]. It means the element at the peak index is greater than its adjacent elements.
• Find Smallest Letter Greater Than Target
  Given a sorted list of lowercase letters letters and a target letter target, you need to find the smallest letter in the list that is greater than the target. If the target is greater than or equal to the last letter in the list, the smallest letter should loop around to the first letter.
• Binary Search Problem
  Binary Search is a classic searching algorithm that efficiently finds the target element in a sorted array. Given a sorted array of integers nums and a target element target, you need to find the index of the target element in the array. If the target element is not present in the array, return -1.
• Single Element in a Sorted Array
  Given a sorted array of integers where every element appears twice except for one, you need to find that single element that appears only once.
• Find First and Last Position of Element in Sorted Array
  Given a sorted array of integers nums and a target element target, you need to find the starting and ending position of target in the array. If the target element is not present in the array, return [-1, -1].
• Search in Rotated Sorted Array
  We can solve this problem using a modified binary search algorithm. We can identify whether the target element lies in the left or right half of the rotated array based on a comparison with the first element. Then, we can perform a regular binary search in the corresponding half to find the target element.
• Find In Mountain Array
  A mountain array is defined as an array that increases to a peak element and then decreases. You need to find the target element target in the mountain array and return its index.