Binary search algorithm

Binary search works on sorted arrays. Main idea is

  1. keep two pointers to track the search scope in an array, i.e. start and end.
  2. divide the search space in three parts [start, mid), [mid, mid], (mid, end], where mid is middle element.
  3. check condition with these ranges
    • if we want the left range, then we repeat the first step, the middle element becomes the new last element.
    • if we want the right range, then we repeat the first step, where the middle element becomes the new first element.
    • else return mid

You can consider ranges [start, mid-1], [mid, mid], [mid+1, end].

Binary search code

guess number game

One player must pick a number, other player must guess the number.

  • player A picks a number from 1 to n.
  • player B guesses which number player A picked. Let's we have function, that return answer of player A:
    • 0 - the picked number is equal to the guessed
    • 1 - the picked number is higher than the guessed
    • -1 - the picked number is lower than the guessed

Constraints:

  • 1 <= n <= 231 - 1
  • 1 <= pick <= n
Guess number game code

search in matrix

Check is a value in a m x n matrix with the following properties:

  • integers in each row are sorted from left to right
  • the first integer of each row is greater than the last integer of the previous row

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

Main idea:

  1. search row, where target can be found
  2. search target in row
Search in matrix code

search in rotated array

Let's we have an sorted array. Then it was rotated by unknown number k.

For example, the array [0,1,2,4,5,6,7] after rotation by k = 4 will be [4,5,6,7,0,1,2].

The task is to return the index of the specified number in the rotated array, or -1 if the number is not in the array.

Main idea is to apply modified binary search algorithm:

  1. search middle index as usual, i.e. mid = (start + end)/2
  2. check conditions:
    • If target == array[mid], return mid
    • check is array[start..mid] is sorted, i.e. array[start] < array[mid], then change a search scope
      • if array[start] <= num <= array[mid], set end = mid-1
      • else set start = mid+1
    • else if array[mid..end] is sorted, i.e. array[mid] < array[end], then change a search scope
      • if array[mid] <= num <= array[end], set start = mid+1
      • else set end = mid-1
    • increase the start by 1 to avoid an infinite loop
Search in rotated array code