Brief description: Since this article, I will start another series, which is to learn a basic algorithm every week mentioned in the last article. I will analyze it based on topics in LeetCode. The solution language is usually Kotlin or Java. If it involves some knowledge about Kotlin, some introduction will be made. If you get into the habit of learning data structure algorithms and brushing questions, it will help you a lot whether you are interviewing for a job or in the real world. That is the purpose of this series.

1. Time complexity

Worst time complexity O(log n)

Optimal time complexity O(1)

Average time complexity O(log n)

2. Basic Ideas

In an ordered list, if the number to be searched is equal to the position in the middle of the list, it means that the number to be searched is found. If the number to be searched is larger than the number in the middle of the list, it means that the number to be searched may be in the latter part of the ordered list. If the number to be searched is less than the number in the middle of the list, the number to be searched may be in the first half of the ordered list. The search range is then shortened in the same way as the above operation until the last number is found. If it is not equal to the number to be searched, the search range is empty.

Three, algorithm steps

Given an array or sequence of n valued elements A[0]… A[n-1], so that A[0] <=… <= A[n-1], and the Target value Target.

  • Set low = 0, high = n-1
  • 2. If low > high, the search fails
  • 3. Set mid(intermediate value element) as (low + high) / 2 to round down (note: in specific implementation, in order to prevent overflow, generally adopt low + (high-low) / 2 to round down or directly use the shift operation of bit operation to realize the division of 2. This will be explained by a specific topic later)
  • If Target > A[mid], set low = mid + 1 and return to Step 2
  • 5. If Target < A[mid], set high = mid-1 (indicating that the value to be searched is in the first half of the sequence or array (except for itself), move the high cursor to narrow the search range) and return to Step 2
  • If Target == A[mid], return mid.

Fourth, algorithm process demonstration

Five, code implementation (Kotlin language description)

Binary search algorithm mainly has two ways of implementation, one is the way of cyclic recurrence, the other is the way of recursion

  • 1.Cyclic recursive implementation
  • 2,Recursive implementation

Mid = (low + high) / 2

It is believed that those who have scanned LeetCode questions may encounter errors exceeding the time limit in the process of scanning binary search questions

O(log n)

  • 1, the cause of the problem

We can determine that both low and high are non-negative numbers, so that the highest sign bit in the binary representation is 0, and that both low and high are integers with 31 bits of binary

Consider the following scenario:

High = 0100 0000 0000 0000 0000 0000 0000 = 1073741824 (half of integer. MAX_VALUE) low = 0100 0000 0000 0000 0000 0000 0000 0000 0000 = 1073741824 (half of integer.max_value)Copy the code

When low + high is performed, the binary operation is performed as follows

high + low = 1000 0000 0000 0000 0000 0000 0000 0000
Copy the code

The result of the above high + low operation is 2147483648 (the size of integer.max_value) if it is an unsigned 32-bit (4-byte)Integer; If it is a signed 32-bit (4 bytes)Integer, it represents -2147483648. It is important to note that unsigned Integer types are not supported in Java or Kotlin, only signed Integer types exist.

In Java or Kotlin, (low + high) / 2 becomes negative — 1073741824, low = mid + 1, low becomes negative The target value is always larger than the mid value, and the low value accumulates until the low value reaches 1073741824, and the mid value changes to -1073741824, which leads to an endless loop and times out. Take a look at this example:

Operation results:

  • 2. The way to solve the problem

You may see two solutions to the above problem, one is to use low + (high-low) / 2, the other is (low + high) >>> 1 or (Low + High) UShr 1 in Kotlin.

(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824
Copy the code

Here’s an example:

Supplement Kotlin and Bit operations in Java

  • 1. The difference between >>> and >> in Java (or USHR and SHR in Kotlin)

In fact, the unsigned right-shift operator >>>(or ushr in Kotlin) is the same as the right-shift operator >>(or SHR in Kotlin), except that the right-shift operator complements the sign bit on the left, whereas the unsigned right-shift operator complements 0

  • 2. Bit operations in Kotlin

Abandoned in the Kotlin Java that directly using the > > > and > >, < <, &, ~, |, ^ these semantic symbol to realize bit operations, to be honest this symbol code readability are indeed reduce a lot, have seen source friend knew, many source in pursuit of the efficiency of the code, tend to adopt a operation, But the code is a little harder to understand and read. Happily, Kotlin uses a more semantically oriented infix to implement bitwise operations, which is really concise and can be used as if you were using an operator, but with more meaning.

Binary search on LeetCode

Note: here are some suggestions before you do binary search.

  • 1, really in the process of doing the problem will rarely directly write standard binary search topic, generally is the need to transform into binary search problems. Therefore, it is more important to master the idea of binary search than to master the way of implementation.
  • 2, the general binary search to solve the problem has a very obvious feature that is the ascending array or ordered array, and in some search numbers, the time complexity requirements are relatively high, for example, the time complexity must be lower than O(n), obviously you can not directly use a loop to do, The average time complexity of binary lookup is O(log n) significantly lower than O(n), so you may need to consider whether binary lookup can be used.
  • 3. Another problem that typically uses binary search is finding square roots or perfect squares. A general conclusion is that the square root of a non-negative number n is less than n/2 + 1. So this translates to finding the square root or perfect square from [0,n/2 + 1].

  • 1. Sum of two numbers II – Enter ordered array

  • 2. Valid perfect squares

  • 3. Square root of x

  • 4, mountain array peak index

  • 5. Standard binary search

  • 6. Find the smallest letter larger than the target letter

  • 7. Guess the size of the number

  • 8. The first incorrect version

  • Find the intersection of two arrays

  • Intersection of two arrays II

Welcome to the Kotlin Developer Association, where the latest Kotlin technical articles are published, and a weekly Kotlin foreign technical article is translated from time to time. If you like Kotlin, welcome to join us ~~~

Welcome to Kotlin’s series of articles:

Original series:

  • How do you fully parse the type system in Kotlin
  • How do you make your callbacks more Kotlin
  • Jetbrains developer briefing (3) Kotlin1.3 new features (inline class)
  • JetBrains developer briefing (2) new features of Kotlin1.3 (Contract and coroutine)
  • Kotlin/Native: JetBrains Developer’s Day (Part 1
  • How to overcome the difficulties of generic typing in Kotlin
  • How to overcome the difficulties of Generic typing in Kotlin (Part 2)
  • How to overcome the difficulties of Generic typing in Kotlin (Part 1)
  • Kotlin’s trick of Reified Type Parameter (Part 2)
  • Everything you need to know about the Kotlin property broker
  • Source code parsing for Kotlin Sequences
  • Complete analysis of Sets and functional apis in Kotlin – Part 1
  • Complete parsing of lambdas compiled into bytecode in Kotlin syntax
  • On the complete resolution of Lambda expressions in Kotlin’s Grammar
  • On extension functions in Kotlin’s Grammar
  • A brief introduction to Kotlin’s Grammar article on top-level functions, infix calls, and destruct declarations
  • How to Make functions call Better
  • On variables and Constants in Kotlin’s Grammar
  • Elementary Grammar in Kotlin’s Grammar Essay

Translated by Effective Kotlin

  • The Effective Kotlin series considers arrays of primitive types for optimal performance (5)
  • The Effective Kotlin series uses Sequence to optimize set operations (4)
  • Exploring inline modifiers in higher-order functions (3) Effective Kotlin series
  • Consider using a builder when encountering multiple constructor parameters in the Effective Kotlin series.
  • The Effective Kotlin series considers using static factory methods instead of constructors (1)

Translation series:

  • Remember a Kotlin official document translation PR(inline type)
  • Exploration of autoboxing and High performance for inline classes in Kotlin (ii)
  • Kotlin inline class full resolution
  • Kotlin’s trick of Reified Type Parameter
  • When should type parameter constraints be used in Kotlin generics?
  • An easy way to remember Kotlin’s parameters and arguments
  • Should Kotlin define functions or attributes?
  • How to remove all of them from your Kotlin code! (Non-empty assertion)
  • Master Kotlin’s standard library functions: run, with, let, also, and apply
  • All you need to know about Kotlin type aliases
  • Should Sequences or Lists be used in Kotlin?
  • Kotlin’s turtle (List) rabbit (Sequence) race

Actual combat series:

  • Use Kotlin to compress images with ImageSlimming.
  • Use Kotlin to create a picture compression plugin.
  • Use Kotlin to compress images.
  • Simple application of custom View picture fillet in Kotlin practice article