Algorithm – search – binary search

The search range

[startIndex,endIndex)

const nums = [3.31.4.9];
for (let i = 0; i < nums.length; i++) {
  const element = nums[i];
  console.log(`==============>element`);
  console.log(element);
}

Copy the code

I =0 to I < nums.length

It should be in mathematical notation

[0,nums.length)

The left-hand side here is the closed interval, because we’re really using 0, which makes sense.

If I == nums.length, I == nums.length, I == nums.length, I == nums.length, I == nums.length, I == nums.length, I == nums.length, I == nums.length

Search interval definition

Now we introduce the concept of a search interval: the range of the change of the subscript I when traversing the entire array is represented by the open and closed interval in mathematical symbols, which is called the search interval.

I made my own definition

Suppose we set the startIndex and endIndex in the range of the search interval for I.

According to the combination of open and closed intervals, there are the following four types of search intervals:

1. [startIndex,endIndex]
2. [startIndex,endIndex)
3. (startIndex,endIndex]
4. (startIndex,endIndex)

The most common traversal method above uses the search interval [startIndex,endIndex]. For better understanding, let’s write down the traversal method for the remaining three search intervals

[startIndex,endIndex]

In [startIndex,endIndex), we are talking about [0,nums.lenght)

• let i = 0The starting point,
• i < nusm.lengthTo the end

• = denotes [closed interval

• < indicates) interval

So what we’re going to do now is [startIndex,endIndex] should be

• let i = 0
• i <= nums.length(error)

• =said[Closed interval
• < =said)Open interval

// Error
const nums = [3.31.4.9];
for (let i = 0; i <= nums.length; i++) {
  const element = nums[i];
  console.log(`==============>element`);
  console.log(element);
}
Copy the code

If I == nums.length, the access to nums[nums.length] will be traversal, which will cause the array access to be out of bounds. To avoid this, we also change I <= nums.length to I <= nums.length -1

I == nums.length -1; I == nums.length -1; nums = nums.length -1;

So the startIndex,endIndex would be

• let i = 0
• i <= nums.length -1

/ / right
const nums = [3.31.4.9];
for (let i = 0; i <= nums.length - 1; i++) {
  const element = nums[i];
  console.log(`==============>element`);
  console.log(element);
}

Copy the code

(startIndex,endIndex]

const nums = [3.31.4.9];
for (let i = nums.length - 1; i >= 0; i--) {
  const element = nums[i];
  console.log(`==============>element`);
  console.log(element);
}

Copy the code

Here we use backward-forward traversal, because we always like [closed interval value as the first traversal, otherwise it is too troublesome

And this is often used when you’re dealing with things like array collapse, where you iterate from the back

(startIndex,endIndex)

const nums = [3.31.4.9];
for (let i = nums.length - 1; i > -1; i--) {
  const element = nums[i];
  console.log(`==============>element`);
  console.log(element);
}

Copy the code

Very rarely, the traversal is determined by the step value, which is 1

[)and[]conclusion

We usually talk about these two intervals in binary search, so let’s summarize the differences between the two

// [startIndex,endIndex)
const nums = [3.31.4.9];
for (let i = 0; i < nums.length; i++) {
  const element = nums[i];
  console.log(`==============>element`);
  console.log(element);
}

Copy the code

// [startIndex,endIndex]
const nums = [3.31.4.9];
for (let i = 0; i <= nums.length - 1; i++) {
  const element = nums[i];
  console.log(`==============>element`);
  console.log(element);
}

Copy the code

Both start with let I = 0, so both are [

To satisfy), I < nums.length is required

To satisfy], I must satisfy I <= nums.length -1

Because we want to keep our array access within bounds, we subtract one

whilecycle

[)

In the for loop, we iterate over the array using let I = 0, whereas in the while loop, we define a search interval and then use only the first value of the search interval to read the array value, for example

1. Define the search interval

let startIndex = 0;
let endIndex = nums.length;
Copy the code

2. throughstartIndexAccess to an array
3. startIndexTo increase

The final code is as follows:

// [startIndex,endIndex)
const nums = [3.31.4.9];
for (let i = 0; i < nums.length; i++) {
  const element = nums[i];
  console.log(`==============>element`);
  console.log(element);
}

let startIndex = 0;
let endIndex = nums.length;
while (startIndex < endIndex) {
  const element = nums[startIndex];
  console.log(`==============>element`);
  console.log(element);
  startIndex++;
}

Copy the code

While (startIndex < endIndex) while (startIndex < endIndex)

With the search interval set up above, when we see

let startIndex = 0;
let endIndex = nums.length;
Copy the code

[startIndex, endIndex] [startIndex, endIndex] [startIndex, endIndex] [startIndex, endIndex] [startIndex, endIndex] [startIndex, endIndex] [startIndex, endIndex

So we have while (startIndex < endIndex) as the loop condition.

[]

Similarly, when we define

let startIndex = 0;
let endIndex = nums.length - 1;
Copy the code

I’m going to think of [startIndex,endIndex] double closed interval, and the loop condition in for is going to be

let i = 0 ; i <= nums.length - 1; i++
Copy the code

So this is going to be converted

while(startIndex <= endIndex)
Copy the code

The final code is as follows

// [startIndex,endIndex]
const nums = [3.31.4.9];
for (let i = 0; i <= nums.length - 1; i++) {
  const element = nums[i];
  console.log(`==============>element`);
  console.log(element);
}

let startIndex = 0;
let endIndex = nums.length - 1;
while (startIndex <= endIndex) {
  const element = nums[startIndex];
  console.log(`==============>element`);
  console.log(element);
  startIndex++;
}

Copy the code

Binary Search

The following is copied in Binary Search

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

In computer science, binary search, also known as half interval search, logarithmic search or binary chopping, is a search algorithm to find the position of the target value in a sorted array. A binary search compares the target value to the intermediate element in the array, and if they are not equal, it strips out the half that the target cannot be, and continues to search the remaining half until the search succeeds. If the search ends and the remaining half is empty, the target is not in the array.

Chinese department machine translation.

Complexity

Time Complexity: O(log(n)) – since we split search area by two for every next iteration.

code

export default function binarySearch(
  sortedArray: number[],
  seekElement: number
) :number {
  // These two indices will contain current array (sub-array) boundaries.
  let startIndex = 0;
  let endIndex = sortedArray.length - 1;

  // Let's continue to split array until boundaries are collapsed
  // and there is nothing to split anymore.
  while (startIndex <= endIndex) {
    // Let's calculate the index of the middle element.
    const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);

    // If we've found the element just return its position.
    if (sortedArray[middleIndex] === seekElement) {
      return middleIndex;
    }

    // Decide which half to choose for seeking next: left or right one.
    if (sortedArray[middleIndex] < seekElement) {
      // Go to the right half of the array.
      startIndex = middleIndex + 1;
    } else {
      // Go to the left half of the array.
      endIndex = middleIndex - 1; }}// Return -1 if we have not found anything.
  return -1;
}

Copy the code

A simplified version of binarySearch

parsing

The loop condition

First of all, we don’t care what the algorithm is in binary search, since the code uses startIndex and endIndex to use arrays, we need to make sure that there are two things, right

• Ensure that access to arrays is not out of bounds
• Make sure that every element is traversed

So if we define it this way

let startIndex = 0;
let endIndex = sortedArray.length - 1;
Copy the code

We immediately think of [] as a doubly closed search interval, so the loop condition of while must be

while(startIndex <= endIndex)
Copy the code

I don’t know why, scroll up again…

So suppose we define it this way?

let startIndex = 0;
let endIndex = sortedArray.length;
Copy the code

The search interval should be [), so the loop condition for while must be

while(startIndex < endIndex)
Copy the code

Interval changes

// If we've found the element just return its position.
if (sortedArray[middleIndex] === seekElement) {
  return middleIndex;
}

// Decide which half to choose for seeking next: left or right one.
if (sortedArray[middleIndex] < seekElement) {
  // Go to the right half of the array.
  startIndex = middleIndex + 1;
} else {
  // Go to the left half of the array.
  endIndex = middleIndex - 1;
}
Copy the code

Why do we need to add one or subtract one to change startIndex and endIndex?

First, according to

let startIndex = 0;
let endIndex = sortedArray.length - 1;
Copy the code

We know that his search interval should be [] double closed.

And then, let’s go with the previous judgment

// If we've found the element just return its position.
if (sortedArray[middleIndex] === seekElement) {
  return middleIndex;
}
Copy the code

Knowing that the subscript middleIndex we have already determined that this value is used and no longer needed.

So, let’s start next time if it’s

startIndex = middleIndex

According to our [] double-closed interval, startIndex will be used again even if we use the midddleIndex value that this loop has already judged.

EndIndex = middleIndex – 1

So at this point in time, if our algorithm starts out being

let startIndex = 0;
let endIndex = sortedArray.length;
Copy the code

The search interval should be [), and the startIndex is the same. To avoid repeating middleIndex, we should set it to [)

startIndex = middleIndex + 1;
Copy the code

We use middleIndex because endIndex is the open interval, but because of the nature of the open interval, we can just put it in, and it must not be subtracted by one

endIndex = middleIndex;
Copy the code

Because if I subtract one

endIndex = middleIndex - 1 ;
Copy the code

1. middleIndex - 1We haven’t used this value before
2. )The nature of the open interval prevents us from using this value

[)Binary search

export default function binarySearch(
  sortedArray: number[],
  seekElement: number
): number {
  // These two indices will contain current array (sub-array) boundaries.
  let startIndex = 0;
- let endIndex = sortedArray.length - 1;
+ let endIndex = sortedArray.length;

  // Let's continue to split array until boundaries are collapsed
  // and there is nothing to split anymore.
- while (startIndex <= endIndex) {
+ while (startIndex < endIndex) {
    // Let's calculate the index of the middle element.
    const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);

    // If we've found the element just return its position.
    if (sortedArray[middleIndex] === seekElement) {
      return middleIndex;
    }

    // Decide which half to choose for seeking next: left or right one.
    if (sortedArray[middleIndex] < seekElement) {
      // Go to the right half of the array.
      startIndex = middleIndex + 1;
    } else {
      // Go to the left half of the array.
- endIndex = middleIndex - 1;
+ endIndex = middleIndex;
    }
  }

  // Return -1 if we have not found anything.
  return -1;
}

Copy the code

Here we find the condition

1. if (sortedArray[middleIndex] === seekElement)
2. if (sortedArray[middleIndex] > seekElement)

The first way to do it is

return middleIndex;
Copy the code

The latter is handled in this way

endIndex = middleIndex;
Copy the code

If endIndex == middleIndex, then endIndex == middleIndex. If endIndex == middleIndex, then endIndex == middleIndex

export default function binarySearch(
sortedArray: number[],
 seekElement: number
) :number {
  let startIndex = 0;
  let endIndex = sortedArray.length;

  while (startIndex < endIndex) {
    const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);

    if (sortedArray[middleIndex] < seekElement) {
      startIndex = middleIndex + 1;
    } else {
      // contains >= two casesendIndex = middleIndex; }}// If no search is found
  if(endIndex === sortedArray.length || sortedArray[endIndex] ! == target) {return -1;
  }

  return endIndex;
}

Copy the code

Here’s an additional logical handle for the missing case:

We know that the final return is endIndex, which is actually middleIndex

And the search interval for this value is [startIndex,endIndex]

So if you can’t find it, there will be

If the target value is less than any element of the array passed in, 0 is returned

If the target value is greater than any element in the passed array, sorteDarray.length is returned

So we should add a judgment at the end

if(endIndex === sortedArray.length || sortedArray[endIndex] ! == target) {return -1;
}
return endIndex;
Copy the code

Value of the boundary

On the left side of the border

Now we’ve written two versions of the dichotomy

• []

const arr = [3.9.9.9.9.9.31.45];
const target = 9;

export default function binarySearch(
  sortedArray: number[],
  seekElement: number
) :number {
  let startIndex = 0;
  let endIndex = sortedArray.length - 1;

  while (startIndex <= endIndex) {
    const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);

    if (sortedArray[middleIndex] === seekElement) {
      return middleIndex;
    }

    if (sortedArray[middleIndex] < seekElement) {
      startIndex = middleIndex + 1;
    } else {
      endIndex = middleIndex - 1; }}return -1;
}
const ret = binarySearch(arr, target);
console.log(`==============>ret`);
console.log(ret); / / 3

Copy the code

• [)

const arr = [3.9.9.9.9.9.31.45];
const target = 9;

export default function binarySearch(
  sortedArray: number[],
  seekElement: number
) :number {
  let startIndex = 0;
  let endIndex = sortedArray.length;

  while (startIndex < endIndex) {
    const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);

    if (sortedArray[middleIndex] < seekElement) {
      startIndex = middleIndex + 1;
    } else {
      // contains >= two casesendIndex = middleIndex; }}if(endIndex == sortedArray.length || sortedArray[endIndex] ! == target) {return -1;
  }
  return endIndex;
}
const ret = binarySearch(arr, target);
console.log(`==============>ret`);
console.log(ret); / / 1

Copy the code

We find that the two notations return different values when there are repeated elements in an ordered data

[] This return 3 is quite understandable, because mid is an intermediate number, so it is easy to be hit in the middle of a group of 9. Once hit, it will return, so it will return a middle number

[) returns the first index of 9 when mid hits while the while continues

because

1. Array ordering (ascending)
2. midIt keeps getting smaller

If sortedArray[middleIndex] is less than or equal to the target value, then startIndex is triggered to the right and endIndex is triggered to the left. StartIndex === endIndex; startIndex == endIndex; startIndex == endIndex;

On the right side of the border

So since we have this left edge right here, can we go the other way, and write a value that gets the right edge?

Up there we said after a hit

1. startInexMove right
2. endIndexLeft.

Finally, sortedArray[startIndex] and sortedArray[endIndex] both hit and fire forever

if(sortedArray[middleIndex] === seekElement){
  endIndex = middleIndex;
}

Copy the code

Since the startIndex is assumed to be constant all the way through the firing phase, the endIndex that depends on the mid has to get smaller and smaller, so it goes to the left.

So if we want to get the value on the right hand side, we’re going to do it in this last phase, which is the constant triggering

To make mid larger, the only way to make mid larger is to make starIndex or endIndex larger. If endIndex becomes larger, it may cause startIndex to fail to catch up with endIndex, so we should make startIndex larger

if (sortedArray[middleIndex] === seekElement) {
  startIndex = middleIndex + 1;
}
Copy the code

So the startIndex is going to be to the right of the hit, and we just have to subtract 1 to get the right edge

export default function binarySearch(
sortedArray: number[],
 seekElement: number
) :number {
  let startIndex = 0;
  let endIndex = sortedArray.length;

  while (startIndex < endIndex) {
    const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);

    if (sortedArray[middleIndex] < seekElement) {
      startIndex = middleIndex + 1;
    } else if (sortedArray[middleIndex] > seekElement) {
      endIndex = middleIndex;
    } else if (sortedArray[middleIndex] === seekElement) {
      startIndex = middleIndex + 1; }}if (sortedArray[startIndex - 1] !== target) return -1;
  return startIndex - 1;
}
Copy the code

Because the range of mid must be the range of the search interval, in this case is [)

StartIndex = middleIndex + 1; startIndex = middleIndex + 1

• The minimum is 0

• The maximum value is sortedarray.length