O(log n) 의 Time complexity

1 3 5 7 8 20 30 // 7칸의 배열

0번째를 Left 6번째를 Right.

pivot = (Left + Right) / 2;

pivot = (0 elem + 6 elem) / 2 = 4번째 인 [3].

찾으려고 하는 수가 20이라 해보자.

L은 20보다 작아야하고, R은 20보다 커야한다.

L < 20 R > 20

5번째 원소가 7이다. 찾으려고 하는 수가 20인데 pivot은 7이므로 무조건 pivot 오른쪽에 있을 것이다. Left를 pivot 다음 포인터로 옮긴다.

Left = pivot + 1;

다시 pivot을 정해준다.

가장 왼쪽이 된 (4elem + 6elem) /2 = 5;

pivot은 20을 카리킨다.

찾으려는 수와 동일해졌다. 20을 return 해주면 된다.

만약 Array에 없는 수를 찾고 있다!

21을 찾는다 하면 pivot의 오른쪽에 있어야 할 것이다. 현재 20을 가리키고 있다고 했다.

Left가 pivot 오른쪽으로 옮겨질 것이다. pivot + 1;

그리고 다시 pivot을 정해보면 L과 R 모두 30을 가리키고 있기 때문에 pivot또한 30을 가리킨다. Right는 30을 가리키다 보니 21은 pivot의 왼쪽에 있다고 생각할 것이다. 그래서 pivot의 왼쪽으로 옮겨진다. pivot -1;

이때 L 과 R의 위치가 역전되었다.