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].

fun binarySearch(nums: IntArray, target: Int): Int {
    if(nums.size==0) return -1
    if(target<nums[0]) return -1
    if(target>nums.last()) return -1

    var minInd =0
    var maxInd =nums.size-1

    while(minInd<=maxInd){
        val ind = (minInd+maxInd)/2 // index of middle element

        when{
            target == nums[ind] -> return ind // found target
            target < nums[ind] -> maxInd = ind-1
            else -> minInd = ind+1
        }      
     }

        return  -1 // element not found
}

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 <= 2³¹ - 1
• 1 <= pick <= n

fun guessNumber(n:Int):Int {
     var start : Int = 1
     var end : Int = n
        
     while(start<end){
         val num = ((start.toLong()+end.toLong())/2L).toInt()
            
         when(guess(num)){
             0 -> return num
             -1 -> end = (num-1)
             1 -> start = (num+1)
         }   
      }
        
    return start
}

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
• -10⁴ <= matrix[i][j], target <= 10⁴

Main idea:

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

fun searchInArray(array: IntArray, target: Int): Boolean {
    // not necessary in our case
    if(target< array[0]) return false
    if(target> array[array.size-1]) return false

    var startInd = 0
    var endInd = array.size-1

    while(startInd<=endInd){
        val ind = (startInd+endInd)/2
        val m = array[ind]

        if(m==target) return true
        else if(target < m) endInd = ind-1
        else startInd = ind+1
    }

    return false
}

fun searchInMatrix(matrix: Array<IntArray>, target: Int): Boolean {
    if( target < matrix[0][0])  return false
    if( target > matrix[matrix.size-1][matrix[0].size-1])   return false

    var startInd = 0
    var endInd = matrix.size-1

    while(startInd <= endInd){
        val ind = (startInd+endInd)/2
        val midArray = matrix[ind]

        when{
            target>= midArray[0] && target <= midArray[midArray.size-1] ->{
                return searchInArray(midArray, target)
            }

            target < midArray[0] -> endInd = ind-1
            target > midArray[midArray.size - 1] -> startInd = ind +1
        }
    }

    return false
}

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

fun search(nums: IntArray, target: Int): Int {
    var start = 0
    var end = nums.lastIndex

    while (start <= end) {

        val ind = (start + end) / 2
        val m = nums[ind]

        if (m == target) return ind

        if (nums[start] < m) {
            if (target < m && nums[start] <= target) {
                end = ind - 1
            } else {
                start = ind + 1
            }
        } else if (m < nums[end]) {
            if (m < target && target <= nums[end]) {
                start = ind + 1
            } else {
                end = ind - 1
            }
        } else ++start 

    }

    return -1
}